线段树标记下传模板

发表于   |  

本身像我这么懒的人是不会去打lazyTag线段树的。。。
但是今天模拟赛的时候看错题了。。。 以为要打线段树
然后就把刘书翻出来再看一遍。。。

刘书上的线段树简直不忍直视。区间加的版本根本就是错误的。。。
区间修改也很鸡肋。。
于是自己打了个模板，目测是正确的。

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
struct segTree{

	int setv[MAXN<<2],sumv[MAXN<<2];
	void init(){
		for (int i=0;i<=(n<<2);i++) setv[i]=-1;
		memset(sumv,0,sizeof sumv);
	}
	void maintain(int o,int l,int r){
		if (setv[o]>=0) sumv[o]=setv[o]*(r-l+1); else 
		if (l<r) sumv[o]=sumv[lc]+sumv[rc];

	}
	void pushdown(int o){
		if (setv[o]>=0){
			setv[lc]=setv[rc]=setv[o];
			setv[o]=-1;
		}
	}
	void update(int o, int l, int r, int tl, int tr, int v){
		if (tl<=l && r<=tr){
			setv[o]=v;
		} else {
			pushdown(o);
			if (tl<=mid) update(lc,l,mid,tl,tr,v); else maintain(lc,l,mid);
			if (tr>mid) update(rc,mid+1,r,tl,tr,v); else maintain(rc,mid+1,r);		
		}	
		maintain(o,l,r);
	}
	int query(int o, int l, int r, int tl, int tr){
		if (tl<=l && r<=tr)	{
			maintain(o,l,r);
			return sumv[o];
		}
		int ret=0;
		pushdown(o);
		if (tl<=mid) ret+=query(lc,l,mid,tl,tr); else maintain(lc,l,mid);
		if (tr>mid) ret+=query(rc,mid+1,r,tl,tr); else maintain(rc,mid+1,r);
		maintain(o,l,r);
		return ret;
	}
}