解題區/解題區 - Zerojudge

b278. 说话不算话的区间求和

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

一个长度为n的数组a[1..n]，初始值为0,。要求你维护三种操作：

1 x v ：把数组的第x个元素改为v；(1≤x≤n,1≤v≤100,000,000)

2 x y ：询问数组元素a[x],a[x+1],…,a[y]之和；(1≤x≤y≤n)

0 k ：撤销最近的k次操作(注意，撤销操作本身也是操作，询问也算一次操作)。(1≤k≤当前操作次数)

Sample Input

1
2
3
4
5
6
2 5
1 1 1
1 2 2
2 1 2
0 2
2 1 2

Sample Output

1
2
3
1

Solution

現在學到了一種可持久化的數據精神，有一種為函數式線段樹，最簡單理解的就是採用修改不改值，而是增加新的節點，而每一次修改最多增加 O(n log n) (延著線段樹走訪路徑增加節點)

也就是說，每一次修改會根據前一次的 root 增加一個新的 root’，這是一個相當重要的一環，每一次修改會產生新的一棵線段樹，而這個新線段樹大部分節點會使用前一個線段樹的節點，因此只要針對走訪不影響的情況下，我們仍然會經過舊有的節點。

這一題最麻煩的是對於版本回溯，對於撤銷操作而言，撤銷操作可以撤銷 “撤銷操作”，因此會不斷地展開原本被撤銷的相關操作，然後又將部分操作撤銷 … 反反覆覆，後來發現只要根據當前的版本號減去要撤銷操作的總數即可返回，因此必須記錄每一次操作的線段樹結果。

套用函數式線段樹就相當簡單了！

感謝 liouzhou_101 的題意指導

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <assert.h>
using namespace std;
#define MAXBUF 8388608
struct Node {
    int lson, rson;
    long long sum;
} node[MAXBUF + 50];
int nodesize = 0;
int root[524288];
int build(int l, int r) {
    if (l > r)  return 0;
    int k = nodesize++;
    node[k].sum = 0;
    node[k].lson = node[k].rson = 0;
    if (l == r) return k;
    int m = (l + r)/2;
    node[k].lson = build(l, m);
    node[k].rson = build(m+1, r);
    return k;
}
int change(int p, int l, int r, int x, int val) {
    int k = nodesize++;
    node[k] = node[p];
    if (l == r) {
        node[k].sum = val;
        return k;
    }
    int m = (l + r)/2;
    if (x <= m)
        node[k].lson = change(node[p].lson, l, m, x, val);
    else
        node[k].rson = change(node[p].rson, m+1, r, x, val);
    node[k].sum = node[node[k].lson].sum + node[node[k].rson].sum;
    return k;
}
long long query(int k, int l, int r, int x, int y) {
    if (x <= l && r <= y)
        return node[k].sum;
    int m = (l + r)/2;
    long long sum = 0;
    if (x <= m) {
        sum += query(node[k].lson, l, m, x, y);
    }
    if (y > m) {
        sum += query(node[k].rson, m+1, r, x, y);
    }
    return sum;
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        
        root[0] = build(1, n);
        
        int pre_ver = 0, cmd, x = 0, y = 0;
        for (int i = 1; i <= m; i++) {
            scanf("%d %d", &cmd, &x);
            if (cmd == 0) {
                y = 0;
                root[i] = root[i - x - 1];
                pre_ver = i;
            } else if (cmd == 1) {
                scanf("%d", &y);
                root[i] = change(root[pre_ver], 1, n, x, y);
                pre_ver = i;
            } else if (cmd == 2){
                scanf("%d", &y);
//                printf("query root = %d\n", root[pre_ver]);
                printf("%lld\n", query(root[pre_ver], 1, n, x, y));
                root[i] = root[pre_ver];
                pre_ver = i;
            }
            if (nodesize > MAXBUF) {
                return 0;
            }
        }
    }
    return 0;
}
/*
 2 5
 1 1 1
 1 2 2
 2 1 2
 0 2
 2 1 2
 */