bzoj 4552 排序

Posted on | Views:

二分 + 线段树.

  • 开始以为是中间有多次询问,想了两节课.读题发现,只在最后询问一次,那就很友好了.
  • 操作/贡献都只与相对大小有关,经典套路就是二分答案,将数列变为 $0/1$ 数列,就可以直接用线段树维护了.
  • 时间复杂度 $O(m\cdot log^2n)$ .

修改操作注意特判 $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
139
140
141
142
143
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,m,q,a[MAXN];
struct SegTree
{
	struct node
	{
		int sum,tag;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.sum=lson.sum+rson.sum;
	}
	void BuildTree(int o,int l,int r,int k)
	{
		root.tag=-1;
		if(l==r)
		{
			if(a[l]>=k)
				root.sum=1;
			else
				root.sum=0;
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid,k);
		BuildTree(o<<1|1,mid+1,r,k);
		pushup(o);
	}
	void Modifiy(int o,int l,int r,int c)
	{
		root.sum=(r-l+1)*c;
		root.tag=c;
	}
	void pushdown(int o,int l,int r)
	{
		if(root.tag!=-1)
		{
			int mid=(l+r)>>1;
			Modifiy(o<<1,l,mid,root.tag);
			Modifiy(o<<1|1,mid+1,r,root.tag);
			root.tag=-1;
		}
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L>R)
			return;
		if(L<=l && r<=R)
		{
			Modifiy(o,l,r,c);
			return;
		}
		pushdown(o,l,r);
		int mid=(l+r)>>1;
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
	int query(int o,int l,int r,int L,int R)
	{
		if(L>R)
			return 0;
		if(L<=l && r<=R)
			return root.sum;
		pushdown(o,l,r);
		int mid=(l+r)>>1;
		int res=0;
		if(L<=mid)
			res+=query(o<<1,l,mid,L,R);
		if(R>mid)
			res+=query(o<<1|1,mid+1,r,L,R);
		return res;
	}
}T;
struct opt
{
	int op,L,R;
}Q[MAXN];
bool check(int k)
{
	T.BuildTree(1,1,n,k);
	for(int i=1;i<=m;++i)
	{
		int L=Q[i].L,R=Q[i].R;
		int tot1=T.query(1,1,n,L,R);
		int tot0=R-L+1-tot1;
		if(Q[i].op==0)
		{
			T.upd(1,1,n,L,L+tot0-1,0);
			T.upd(1,1,n,L+tot0,R,1);
		}
		else
		{
			T.upd(1,1,n,L,L+tot1-1,1);
			T.upd(1,1,n,L+tot1,R,0);
		}
	}
	return (bool)(T.query(1,1,n,q,q));
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=m;++i)
	{
		Q[i].op=read();
		Q[i].L=read();
		Q[i].R=read();
	}
	q=read();
	int L=1,R=n,ans=-1;
	while(L<=R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
			ans=mid,L=mid+1;
		else
			R=mid-1;
	}
	cout<<ans<<endl;
	return 0;
}