【主席树维护区间修改】HDU 4348 To the moon
2021-08-08 14:23:00 # ACM

题链

普通主席树一般是单点修改，同时增加$logn$个节点，要进行区间修改为了节省空间，于是在主席树上打永久标记，一次区间修改得打$log(r-l+1)$个标记，求和的时候从上至下带着标记求和；

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
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
	#define ls rt<<1
	#define rs rt<<1|1
	#define eps 1e-9
	#define mod 1000000007
	#define MAXN 1e18
	#define MS 100005

int n,m;
struct node{
	int l,r;
	LL sum,tag;
}p[MS<<5];
int rtpos[MS], tot;
int ver;

void push_up(int rt,int l,int r){
	p[rt].sum = p[p[rt].l].sum + p[p[rt].r].sum + (LL)(r-l+1)*p[rt].tag;
}

int build(int l,int r){
	int rt = ++tot;
	p[rt] = {0,0,0,0};
	if(l == r){
		cin >> p[rt].sum;
		return rt;
	}
	int m = l+r>>1;
	p[rt].l = build(l,m);
	p[rt].r = build(m+1,r);
	push_up(rt,l,r);
	return rt;
}

int add(int lart,int L,int R,int l,int r,LL val){
	int rt = ++tot;
	p[rt] = p[lart];
	if(L <= l && r <= R){
		p[rt].sum += (LL)(r-l+1)*val;
		p[rt].tag += val;
		return rt;
	}
	int m = l+r>>1;
	if(m >= L) p[rt].l = add(p[lart].l,L,R,l,m,val);
	if(m <  R) p[rt].r = add(p[lart].r,L,R,m+1,r,val);
	push_up(rt,l,r);
	return rt;
}

LL query(int rt,int L,int R,int l,int r,LL tagsum){
	if(L <= l && r <= R){
 		return p[rt].sum + (LL)(r-l+1)*tagsum;
	}
	tagsum += p[rt].tag;
	int m = l+r>>1;
	LL ans = 0;
	if(m >= L) ans += query(p[rt].l,L,R,l,m,tagsum);
	if(m <  R) ans += query(p[rt].r,L,R,m+1,r,tagsum);
	return ans;
}

void solve(){
//	cin >> n >> m;
	tot = 0;
	rtpos[0] = build(1,n);
	ver = 0;
	while(m--){
		char op;
		int l,r;
		LL x;
		cin >> op;
		if(op == 'Q'){
			cin >> l >> r;
			cout << query(rtpos[ver],l,r,1,n,0ll) << "\n";
		} 
		else if(op == 'C'){
			cin >> l >> r >> x;
			rtpos[ver+1] = add(rtpos[ver],l,r,1,n,x);
			ver++;
		} 
		else if(op == 'H'){
			cin >> l >> r >> x;
			cout << query(rtpos[x],l,r,1,n,0ll) << "\n";
		}
		else if(op == 'B'){
			cin >> x;
			ver = x;
		}
	}
} 

int main() {
	ios::sync_with_stdio(false);
	int ce;
	ce = 1;
//	cin >> ce;
//	scanf("%d",&ce);
//	while(ce--){
//		solve();
//	}
	while(cin >> n >> m){
		solve();
	}



	return 0;
}
/*


*/
Prev
2021-08-08 14:23:00 # ACM
Next