線段樹
A simple problem? 當真?
（雖然是個模板題…）
就是線段樹模板題，需要建出一棵支援區間修改、區間查詢的線段樹。
使用懶標記實現。
本題測資範圍較大，必須開 long long int。
還有使用 cin, cout 時，
請配合
ios::sync_with_stdio(false);
cin.tie(0);
使用，以免 TLE
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char buff[50000000];
long long int seg[500100];
long long int lazy[500100];
void init() {
memset(buff,0x00,sizeof(buff));
memset(seg,0x00,sizeof(seg));
memset(lazy,0x00,sizeof(lazy));
}
void push(int idx, int L, int M, int R) {
if(lazy[idx]==0LL) return;
// 壓懶標記
lazy[idx<<1] += lazy[idx];
lazy[idx<<1|1] += lazy[idx];
seg[idx<<1] += lazy[idx]*(long long int)(M-L+1);
seg[idx<<1|1] += lazy[idx]*(long long int)(R-M);
lazy[idx] = 0LL; // reset lz tag
}
void pull(int idx, int L, int M, int R) {
seg[idx] = seg[idx<<1|1]+seg[idx<<1];
}
void update(int L, int R, int qL, int qR, int idx, long long int val) {
if (L>qR || R<qL) return;
if (L>=qL && R<=qR) {
seg[idx]+=(val*(R-L+1));
lazy[idx]+=val;
return; // 放懶標
}
int M = L+((R-L)>>1);
push(idx, L, M, R);
update(L, M, qL, qR, idx<<1, val);
update(M+1, R, qL, qR, idx<<1|1, val);
pull(idx, L, M, R);
}
long long query(int L, int R, int qL, int qR, int idx) {
if (L>qR || R<qL) return 0LL;
if (L>=qL && R<=qR) return seg[idx];
int M = L+((R-L)>>1);
push(idx, L, M, R);
long long l=0, r=0;
l = query(L,M,qL,qR,idx<<1);
r = query(M+1,R,qL,qR,idx<<1|1);
pull(idx, L, M, R);
return l+r;
}
#define RL() fgets(buff, sizeof(buff)-100, stdin)
int main(void) {
int N, Q, i;
char *readPtr=NULL;
RL();
sscanf(buff, "%d%d", &N, &Q);
RL();
i=1;
readPtr = strtok(buff, " \n");
while(readPtr) {
long long int input=0;
sscanf(readPtr, "%lld", &input);
update(1, N, i, i, 1, input);
readPtr = strtok(NULL, " \n");
++i;
}
while(Q--) {
char op;
int l, r;
long long int x;
RL();
int cnt = sscanf(buff, "%1c %d %d %lld", &op, &l, &r, &x);
if (cnt==4) { //update
update(1, N, l, r, 1, x);
} else {
printf("%lld\n", query(1,N,l,r,1));
}
}
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long int seg[1500100];
long long int lazy[1500100];
#define push(idx, L, M, R) \
if(lazy[idx]!=0LL) { \
lazy[idx<<1] += lazy[idx]; \
lazy[idx<<1|1] += lazy[idx]; \
seg[idx<<1] += lazy[idx]*(long long int)(M-L+1); \
seg[idx<<1|1] += lazy[idx]*(long long int)(R-M); \
lazy[idx] = 0LL; }
#define pull(idx) \
{ seg[idx] = seg[idx<<1|1]+seg[idx<<1]; }
void update(int L, int R, int qL, int qR, int idx, long long int val) {
if (L>qR || R<qL) return;
if (L>=qL && R<=qR) {
seg[idx]+=(val*(R-L+1));
lazy[idx]+=val;
return; // 放懶標
}
int M = L+((R-L)>>1);
push(idx, L, M, R);
update(L, M, qL, qR, idx<<1, val);
update(M+1, R, qL, qR, idx<<1|1, val);
pull(idx);
}
long long query(int L, int R, int qL, int qR, int idx) {
if (L>qR || R<qL) return 0LL;
if (L>=qL && R<=qR) return seg[idx];
int M = L+((R-L)>>1);
push(idx, L, M, R);
long long l=0, r=0;
l = query(L,M,qL,qR,idx<<1);
r = query(M+1,R,qL,qR,idx<<1|1);
pull(idx);
return l+r;
}
#undef push
#undef pull
int main(void) {
int N, Q, i;
scanf("%d", &N);
for (i=1; i<=N; ++i) {
long long int input;
scanf("%lld", &input);
update(1, N, i, i, 1, input);
}
scanf("%d", &Q);
while(Q--) {
int op;
int l, r;
long long int x;
scanf("%d%d%d", &op, &l, &r);
switch (op) {
case 1:
scanf("%lld", &x);
update(1, N, l, r, 1, x);
break;
case 2:
printf("%lld\n", query(1,N,l,r,1));
break;
}
}
return 0;
}