【线段树】The Street

线段树

传送门：CodeChef-STREETTA

题意：给定两个数列，数列A开始为-INF，数列B开始为0，要求支持3种操作：数列A区间与等差数列取max；数列B区间加等差数列；单点查询。

思路：

  • 由于是单点查询，可以考虑标记永久化；
  • 考虑用线段树：对于等差数列的标记，可以记录四个关键字L,R,p,q，由L,R可确定范围，p表示公差，q表示首项；
  • 对于第1种操作，可以发现两个等差数列取max，必定有一个不起作用或只在某半区间起作用（一次函数），可将这个在半个区间起作用的标记下传，这样线段树上的每个节点都只对应一个等差数列。由于标记永久化，求答案时取每层的最大值即可；
  • 对于第2种操作，区间加简单的要死啊；
  • 对于第3中操作，好像没什么好说的。

注意：

  • 标记永久化简化思路，询问时不要下传；
  • 注意标记的实际含义，不要把区间标记的首项和下传标记搞错。

代码如下：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
 
using namespace std;
 
#define LL long long
#define INF (LL)2e18
#define N 600080
 
LL n,m,tot,x,y,p,q,op,root,a[N*30][2],b[N*30][2],vis[N*30],ls[N*30],rs[N*30];
 
void cov(LL &rt,LL l,LL r,LL L,LL R,LL p,LL q){
	if (rt==0) rt=++tot;
	if (L<=l && R>=r){
		LL mid=(l+r)>>1;
		if (vis[rt]==0){
			vis[rt]=1;
			a[rt][0]=p; a[rt][1]=p*(l-L)+q;
			return;
		}
		if (a[rt][1]>=p*(l-L)+q && a[rt][1]+a[rt][0]*(r-l)>=p*(r-L)+q) return;//分清标记端点
		if (a[rt][1]<=p*(l-L)+q && a[rt][1]+a[rt][0]*(r-l)<=p*(r-L)+q){
			a[rt][0]=p; a[rt][1]=p*(l-L)+q; return;
		}
		if (a[rt][1]>=p*(l-L)+q && a[rt][1]+a[rt][0]*(mid-l)>=p*(mid-L)+q){
			cov(rs[rt],mid+1,r,L,R,p,q); return;
		}
		if (a[rt][1]<=p*(l-L)+q && a[rt][1]+a[rt][0]*(mid-l)<=p*(mid-L)+q){
			cov(rs[rt],mid+1,r,l,r,a[rt][0],a[rt][1]);
			a[rt][0]=p; a[rt][1]=p*(l-L)+q; return;
		}
		if (a[rt][1]+a[rt][0]*(mid+1-l)>=p*(mid+1-L)+q && a[rt][0]*(r-l)+a[rt][1]>=p*(r-L)+q){
			cov(ls[rt],l,mid,L,R,p,q); return;
		}
		if (a[rt][1]+a[rt][0]*(mid+1-l)<=p*(mid-1-L)+q && a[rt][0]*(r-l)+a[rt][1]<=p*(r-L)+q){
			cov(ls[rt],l,mid,l,r,a[rt][0],a[rt][1]);
			a[rt][0]=p; a[rt][1]=p*(l-L)+q; return;
		}
		return;
	}
	LL mid=(l+r)>>1;
	if (L<=mid) cov(ls[rt],l,mid,L,R,p,q);
	if (R>mid) cov(rs[rt],mid+1,r,L,R,p,q);
}
 
void add(LL &rt,LL l,LL r,LL L,LL R,LL p,LL q){
	if (rt==0) rt=++tot;
	if (L<=l && R>=r){
		b[rt][0]+=p; b[rt][1]+=(l-L)*p+q;
		return;
	}
	LL mid=(l+r)>>1;
	if (L<=mid) add(ls[rt],l,mid,L,R,p,q);
	if (R>mid) add(rs[rt],mid+1,r,L,R,p,q);
}
 
LL query1(LL rt,LL l,LL r,LL x){
	if (l==r){if (!vis[rt]) return -INF;return a[rt][1];}
	
	LL mid=(l+r)>>1,tmp=vis[rt]?a[rt][0]*(x-l)+a[rt][1]:-INF;
	
	if (x<=mid) return max(tmp,query1(ls[rt],l,mid,x));
	if (x>mid) return max(tmp,query1(rs[rt],mid+1,r,x));
	return -INF;
}
 
LL query2(LL rt,LL l,LL r,LL x){
	if (l==r) return b[rt][1];
	
	LL mid=(l+r)>>1;
	
	if (x<=mid) return b[rt][0]*(x-l)+b[rt][1]+query2(ls[rt],l,mid,x);
	if (x>mid) return b[rt][0]*(x-l)+b[rt][1]+query2(rs[rt],mid+1,r,x);
	return -INF;
}
 
int main(){
	scanf("%lld%lld",&n,&m);
	for (LL i=1;i<=m;i++){
		scanf("%lld",&op);
		if (op==1){
			scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
			cov(root,1,n,x,y,p,q);
		}
		if (op==2){
			scanf("%lld%lld%lld%lld",&x,&y,&p,&q);
			add(root,1,n,x,y,p,q);
		}
		if (op==3){
			scanf("%lld",&x);
			p=query1(root,1,n,x);
			q=query2(root,1,n,x);
			if (p==-INF) puts("NA");
			else printf("%lld\n",p+q);
		}
	}
	
	return 0;
}