「ZJOI模拟赛」线段树

发表于 | 分类于 | | 浏览量： 次

骚年，你只要种一棵主席树和两棵线段树就能A了这题了，多环保啊！

题面

出于一些原因，这里不放题面。

题解

考虑询问的实质。

其实询问的答案必然是序列A中一整段连续区间的最大值。

将$m$个操作进行处理，每个操作都往离它最近的有交集的两个操作（一个操作向左延伸，一个向右）建边。

然后询问的时候倍增，就能很快找到询问实际的左右边界。

用主席树又可以很快找到一个点在操作区间$[L,R]$中最后覆盖它的是哪一个操作。

于是乎建边的时候开一棵线段树，维护全局最大值的时候再开一棵，一共三棵树。

然后就好了。

代码

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005,LOG=18;
int n,m,q,A[maxn],QL[maxn],QR[maxn],FL[maxn][LOG],FR[maxn][LOG];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
struct SegmentTree
{
	struct Node{int Max,Tag;}Tree[maxn*4];
	inline void PushUp(int rt){Tree[rt].Max=max(Tree[rt*2].Max,Tree[rt*2+1].Max);}
	inline void PushDown(int rt)
	{
		if(Tree[rt].Tag==0) return;
		Tree[rt*2].Max=Tree[rt].Tag;Tree[rt*2+1].Max=Tree[rt].Tag;
		Tree[rt*2].Tag=Tree[rt].Tag;Tree[rt*2+1].Tag=Tree[rt].Tag;
		Tree[rt].Tag=0;
	}
	inline void RangeUpdate(int LL,int RR,int num,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR){Tree[rt].Max=Tree[rt].Tag=num;return;}
		PushDown(rt);
		int M=(L+R)>>1;
		if(LL<=M) RangeUpdate(LL,RR,num,L,M,rt*2);
		if(M<RR) RangeUpdate(LL,RR,num,M+1,R,rt*2+1);
		PushUp(rt);
	}
	inline int RangeQuery(int LL,int RR,int L=1,int R=n,int rt=1)
	{
		if(LL<=L&&R<=RR) return Tree[rt].Max;
		PushDown(rt);
		int M=(L+R)>>1,ret=0;
		if(LL<=M) ret=max(ret,RangeQuery(LL,RR,L,M,rt*2));
		if(M<RR) ret=max(ret,RangeQuery(LL,RR,M+1,R,rt*2+1));
		return ret;
	}
	void Build(int* A,int L=1,int R=n,int rt=1)
	{
		if(L==R){Tree[rt].Max=A[L];return;}
		int M=(L+R)>>1;
		Build(A,L,M,rt*2);
		Build(A,M+1,R,rt*2+1);
		PushUp(rt);
	}
}TA,TB;
struct ChairmanTree
{
	int tot,R[maxn];
	struct Node{int L,R,Val;}Tree[maxn*4*LOG];
	int New(){return ++tot;}
	void Build(int rt,int L=1,int R=n)
	{
		if(L==R) return;
		if(rt==1) this->R[0]=1;
		Tree[rt].L=New();
		Tree[rt].R=New();
		int M=(L+R)>>1;
		Build(Tree[rt].L,L,M);
		Build(Tree[rt].R,M+1,R);
	}
	void RangeUpdate(int LL,int RR,int num,int pre,int rt,int L=1,int R=n)
	{
		Tree[rt]=Tree[pre];
		if(LL<=L&&R<=RR){Tree[rt].Val=num;return;}
		int M=(L+R)>>1;
		if(LL<=M)
		{
			Tree[rt].L=New();
			RangeUpdate(LL,RR,num,Tree[pre].L,Tree[rt].L,L,M);
		}
		if(M<RR)
		{
			Tree[rt].R=New();
			RangeUpdate(LL,RR,num,Tree[pre].R,Tree[rt].R,M+1,R);
		}
	}
	int Query(int P,int rt,int L=1,int R=n)
	{
		if(L==R) return Tree[rt].Val;
		int M=(L+R)>>1,ret=Tree[rt].Val;
		if(P<=M) return max(ret,Query(P,Tree[rt].L,L,M));
		else return max(ret,Query(P,Tree[rt].R,M+1,R));
	}
}TC;
int main()
{
	freopen("segment.in","r",stdin);
	freopen("segment.out","w",stdout);
	n=read();m=read();q=read();
	for(int i=1;i<=n;i++) A[i]=read();
	TA.Build(A);
	TC.Build(TC.New());
	for(int i=1;i<=m;i++)
	{
		QL[i]=read();QR[i]=read();
		FL[i][0]=TB.RangeQuery(QL[i],QL[i]);
		FR[i][0]=TB.RangeQuery(QR[i],QR[i]);
		TC.R[i]=TC.New();
		TC.RangeUpdate(QL[i],QR[i],i,TC.R[i-1],TC.R[i]);
		TB.RangeUpdate(QL[i],QR[i],i);
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=16;j++)
		{
			FL[i][j]=FL[FL[i][j-1]][j-1];
			FR[i][j]=FR[FR[i][j-1]][j-1];
		}
	}
	while(q--)
	{
		if(read()==1)
		{
			int u=read(),v=read();
			TA.RangeUpdate(u,u,v);
		}
		else
		{
			int L=read(),R=read(),K=read();
			int Lm=TC.Query(K,TC.R[R]),Rm=Lm;
			if(Lm<L) Lm=Rm=0;
			for(int i=16;i>=0;i--)
			{
				if(FL[Lm][i]>=L) Lm=FL[Lm][i];
				if(FR[Rm][i]>=L) Rm=FR[Rm][i];
			}
			Lm=QL[Lm];Rm=QR[Rm];
			if(Lm>0) printf("%d\n",TA.RangeQuery(Lm,Rm));
			else printf("%d\n",TA.RangeQuery(K,K));
		}
	}
	return 0;
}