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
| namespace Segtree{
#define lson (way<<1)
#define rson (way<<1|1)
#define mid (l+r)/2
int seg[MAXN<<2],lz[MAXN<<2];
inline void build(int way,int l, int r){
if (l==r) {seg[way] = pos[l];return;}
build(lson,l,mid);
build(rson,mid+1,r);
seg[way] = seg[lson]+seg[rson];
}
inline void push(int way, int l, int r){
if (lz[way]==0) return;
seg[way]+=lz[way]*(r-l+1);
if (l!=r)lz[lson]+=lz[way],lz[rson]+=lz[way];
lz[way] = 0;
}
inline void update(int way, int l, int r, int qlow,int qhigh, int val){
push(way,l,r);
if (qlow<=l && r<=qhigh){
lz[way] += val;
push(way,l,r);
return;
}
if (l>qhigh || r<qlow) return;
update(lson,l,mid,qlow,qhigh,val);
update(rson,mid+1,r,qlow,qhigh,val);
seg[way] = seg[lson]+seg[rson];
}
inline int query(int way, int l, int r, int qlow,int qhigh){
push(way,l,r);
if (qlow<=l && r<=qhigh) return seg[way];
if (l>qhigh || r<qlow) return 0;
return query(lson,l,mid,qlow,qhigh)+query(rson,mid+1,r,qlow,qhigh);
}
#undef lson
#undef rson
#undef mid
};
|
