線段樹 + 一些持久化精神
參考 Morris 大神的文章，所以 code 可能有 87% 像 :P
（感謝 Morris 大神寫了很好的文章，他的 code 排版清楚，命名也好理解 XD）
每次操作都是建立一個新節點，因此可以回溯。
詢問時參考新舊節點的值，修改時也會參考舊節點產生新節點。
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
96
97
98
99
100
101
102
// verdict: AC
// time: 0.3s
// memory: 1.5MB
#pragma GCC target ("avx")
#pragma GCC optimize ("Os")
#include <bits/stdc++.h>
using namespace std;
struct Node {
int lc, rc;
long long val;
};
struct SegmentTreeP {
enum { MAXNODE=6101010, MAXREC=500010};
int nodeNum;
int his[MAXREC];
Node sg[MAXNODE];
SegmentTreeP() : nodeNum(0) { }
int build(int l, int r) {
if (l>r) return 0; // illegal
int k = nodeNum++; // allocate new node
sg[k].lc = sg[k].rc = sg[k].val = 0;
if (l==r) return k;
int m = l+((r-l)>>1);
sg[k].lc = build(l, m);
sg[k].rc = build(m+1, r);
return k;
}
void init(int N) {
memset(his,0x00,sizeof(his[0])*MAXREC);
memset(sg, 0x00,sizeof(sg[0])*MAXNODE);
nodeNum = 0;
his[0] = build(1,N);
}
int update(int acs, int l, int r, int q, long long val) {
if (l>r) return 0;
int k = nodeNum++;
sg[k] = sg[acs]; // new node derived from acs
if (l==r) { // modify
sg[k].val = val;
return k;
}
int m = l+((r-l)>>1);
if (q<=m)
sg[k].lc = update(sg[acs].lc, l, m, q, val);// update left
else
sg[k].rc = update(sg[acs].rc, m+1, r, q, val);// update right
sg[k].val= sg[sg[k].lc].val + sg[sg[k].rc].val; // update
return k;
}
long long query(int l, int r, int ql, int qr, int q) {
if (l>r || l>qr || r < ql) return 0LL; // illegal
if (l>=ql && r<=qr) { // in range
return sg[q].val;
}
int m = l+((r-l)>>1);
long long res = 0;
if (ql<=m)
res += query(l, m, ql, qr, sg[q].lc);
if (m< qr)
res += query(m+1, r, ql, qr, sg[q].rc);
return res;
}
};
int main(void) {
SegmentTreeP *newTree = NULL;
newTree = new SegmentTreeP();
assert(newTree!=NULL);
SegmentTreeP &tree = *newTree;
int N, Q;
while(scanf("%d%d", &N, &Q)==2) {
tree.init(N);
int preVer = 0;
for (int i=1; i<=Q; ++i) {
int op, l, r;
scanf("%d%d", &op, &l);
switch(op) {
case 0: {
int rec = max(0, i-l-1);
tree.his[i] = tree.his[rec];
preVer = i;
}
break;
case 1:
scanf("%d", &r);
tree.his[i] = tree.update(tree.his[preVer], 1,N,l,r);
preVer = i;
break;
case 2:
scanf("%d", &r);
printf("%lld\n", tree.query(1,N,l,r,tree.his[preVer]));
tree.his[i] = tree.his[preVer];
preVer = i;
break;
}
}
}
delete newTree;
return 0;
}
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
96
// GCC: ANSI C
#pragma GCC target ("avx")
#pragma GCC optimize ("Os")
#define max(a,b) ((a)>(b)?(a):(b))
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
int lc, rc;
long long val;
} Node;
#define MAXNODE 5101010
#define MAXREC 500010
int nodeNum;
int his[MAXREC];
Node sg[MAXNODE];
int build(int l, int r) {
if (l>r) return 0; /* illegal */
int k = nodeNum++; /* allocate new node */
sg[k].lc = sg[k].rc = sg[k].val = 0;
if (l==r) return k;
int m = l+((r-l)>>1);
sg[k].lc = build(l, m);
sg[k].rc = build(m+1, r);
return k;
}
void init(int N) {
memset(his,0x00,sizeof(his[0])*MAXREC);
memset(sg, 0x00,sizeof(sg[0])*MAXNODE);
nodeNum = 0;
his[0] = build(1,N);
}
int update(int acs, int l, int r, int q, long long val) {
if (l>r || q<l || q>r) return 0;
int k = nodeNum++;
sg[k] = sg[acs]; /* new node derived from acs */
if (l==r) { /* modify */
sg[k].val = val;
return k;
}
int m = l+((r-l)>>1);
if (q<=m)
sg[k].lc = update(sg[acs].lc, l, m, q, val);/* update left */
else
sg[k].rc = update(sg[acs].rc, m+1, r, q, val);/* update right */
sg[k].val= sg[sg[k].lc].val + sg[sg[k].rc].val; /* update */
return k;
}
long long query(int l, int r, int ql, int qr, int q) {
if (l>r || l>qr || r < ql) return 0LL; /* illegal */
if (l>=ql && r<=qr) { /* in range */
return sg[q].val;
}
int m = l+((r-l)>>1);
long long res = 0;
if (ql<=m)
res += query(l, m, ql, qr, sg[q].lc);
if (m< qr)
res += query(m+1, r, ql, qr, sg[q].rc);
return res;
}
int main(void) {
int N, Q;
while(scanf("%d%d", &N, &Q)==2) {
init(N);
int preVer = 0;
int i=0;
for (i=1; i<=Q; ++i) {
int op, l, r;
scanf("%d%d", &op, &l);
switch(op) {
case 0: {
int rec = max(0, i-l-1);
his[i] = his[rec];
preVer = i;
}
break;
case 1:
scanf("%d", &r);
his[i] = update(his[preVer], 1,N,l,r);
preVer = i;
break;
case 2:
scanf("%d", &r);
printf("%lld\n", query(1,N,l,r,his[preVer]));
his[i] = his[preVer];
preVer = i;
break;
}
}
}
return 0;
}