【线段树】V

线段树

传送塔：UOJ164

清华集训2015

题意：给出一个序列要求支持3种操作，区间加，区间减后与0取max，区间赋值，询问单点值

对于前3种操作，可以找到一个统一的lazy标记

对于区间标记cov(a,b)，表示max(x+a,b)（x为元素值），那么：

  • 操作1可表示为cov(x,-INF)
  • 操作2可表示为cov(-x,0)
  • 操作3可表示为cov(-INF,x)

标记合并时cov(a,b)->cov(c,d)=cov(a+c,max(b+c,d))

可以发现这个标记满足结合律

cov(a,b)->cov(c,d)->cov(e,f)=cov(a,b)->(cov(c,d)->cov(e,f))

所以可以lazy tag

注意：

传递历史最大值的tag时要把子节点的当前cov值加在当前节点历史cov值前面合并；

由于操作3可能会一直-INF，cov过小时没有意义，直接和-INF取max

代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
#define INF (LL)1<<60
#define N 1200000
LL n,m,op,x,y,z,cov[N*2][2],cov2[N*2][2],a[N];
inline void pushdown(LL x){
	for (LL i=0,y=x<<1|i;i<2;i++,y=x<<1|i){
		cov2[y][0]=max(cov2[y][0],cov[y][0]+cov2[x][0]);
		cov2[y][1]=max(cov2[y][1],max(cov[y][1]+cov2[x][0],cov2[x][1]));
		cov[y][0]=max(cov[y][0]+cov[x][0],-INF);
		//------当cov标记过小时没有意义，与-INF取max，否则会RE 
		cov[y][1]=max(cov[y][1]+cov[x][0],cov[x][1]);
	}
	cov[x][0]=cov[x][1]=cov2[x][0]=cov2[x][1]=0;		
}
void change(LL x,LL l,LL r,LL L,LL R,LL p,LL q){
	if (L<=l && R>=r){
		cov[x][0]=max(cov[x][0]+p,-INF); cov[x][1]=max(cov[x][1]+p,q);
		cov2[x][0]=max(cov2[x][0],cov[x][0]); cov2[x][1]=max(cov2[x][1],cov[x][1]);
		return;
	}
	pushdown(x);
	LL mid=(l+r)>>1;
	if (L<=mid) change(x<<1,l,mid,L,R,p,q);
	if (R>mid) change(x<<1|1,mid+1,r,L,R,p,q);
}
LL query(LL x,LL l,LL r,LL k){
	if (l==r) return max(cov[x][0]+a[k],cov[x][1]);
	pushdown(x);
	LL mid=(l+r)>>1;
	if (k<=mid) return query(x<<1,l,mid,k);
	if (k>mid) return query(x<<1|1,mid+1,r,k);
	return 0;
}
LL ask(LL x,LL l,LL r,LL k){
	if (l==r) return max(cov2[x][0]+a[k],cov2[x][1]);
	pushdown(x);
	LL mid=(l+r)>>1;
	if (k<=mid) return ask(x<<1,l,mid,k);
	if (k>mid) return ask(x<<1|1,mid+1,r,k);
	return 0;
}
	
int main(){
	scanf("%lld%lld",&n,&m);
	for (LL i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (LL i=1;i<=m;i++){
		scanf("%lld",&op);
		if (op==1){
			scanf("%lld%lld%lld",&x,&y,&z);
			change(1,1,n,x,y,z,-INF);
		}
		if (op==2){
			scanf("%lld%lld%lld",&x,&y,&z);
			change(1,1,n,x,y,-z,0);
		}
		if (op==3){
			scanf("%lld%lld%lld",&x,&y,&z);
			change(1,1,n,x,y,-INF,z);
		}
		if (op==4){
			scanf("%lld",&x);
			printf("%lld\n",query(1,1,n,x));
		}
		if (op==5){
			scanf("%lld",&x);
			printf("%lld\n",ask(1,1,n,x));
		}
	}
	
	return 0;
}