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
|
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int N=30000+100;
int a[N],w[N];
struct SegmentTree
{
#define lson (now<<1)
#define rson (now<<11)
#define mid ((now_l+now_r)>>1)
static const int M=N<<2;
int sum[M][2],lazy[M];
inline void update(int now)
{
sum[now][0]=sum[lson][0]+sum[rson][0];
sum[now][1]=sum[lson][1]+sum[rson][1];
}
inline void pushdown(int now,int now_l,int now_r)
{
if(now_l==now_r)
{
lazy[now]=2;
return;
}
lazy[lson]=lazy[rson]=lazy[now];
sum[lson][lazy[now]]=mid-now_l+1,sum[lson][!lazy[now]]=0;
sum[rson][lazy[now]]=now_r-mid,sum[rson][!lazy[now]]=0;
lazy[now]=2;
}
void Build(int now,int now_l,int now_r)
{
sum[now][0]=sum[now][1]=0;
lazy[now]=2;
if(now_l==now_r)
{
sum[now][w[now_l]]++;
return;
}
Build(lson,now_l,mid);
Build(rson,mid+1,now_r);
update(now);
}
void Change(int L,int R,int x,int now,int now_l,int now_r)
{
if(L>R) return;
if(lazy[now]!=2) pushdown(now,now_l,now_r);
if(now_l>=L and now_r<=R)
{
sum[now][x]=now_r-now_l+1,sum[now][!x]=0;
lazy[now]=x;
return;
}
if(L<=mid) Change(L,R,x,lson,now_l,mid);
if(R>mid) Change(L,R,x,rson,mid+1,now_r);
update(now);
}
int Query(int L,int R,int x,int now,int now_l,int now_r)
{
if(lazy[now]!=2) pushdown(now,now_l,now_r);
if(now_l>=L and now_r<=R)
return sum[now][x];
int ans=0;
if(L<=mid) ans+=Query(L,R,x,lson,now_l,mid);
if(R>mid) ans+=Query(L,R,x,rson,mid+1,now_r);
return ans;
}
#undef lson
#undef rson
#undef mid
}sgt;
struct OP
{
int type,L,R;
}op[N];
int n,m,p;
bool Check(int x)
{
for(int i=1;i<=n;i++)
if(a[i]>=x) w[i]=1;
else w[i]=0;
sgt.Build(1,1,n);
for(int i=1;i<=m;i++)
{
int cnt0=sgt.Query(op[i].L,op[i].R,0,1,1,n),cnt1=op[i].R-op[i].L+1-cnt0;
if(op[i].type==0)
sgt.Change(op[i].L,op[i].L+cnt0-1,0,1,1,n),
sgt.Change(op[i].L+cnt0,op[i].R,1,1,1,n);
else
sgt.Change(op[i].L,op[i].L+cnt1-1,1,1,1,n),
sgt.Change(op[i].L+cnt1,op[i].R,0,1,1,n);
}
if(sgt.Query(p,p,1,1,1,n)==1) return true;
return false;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
op[i].type=read(),op[i].L=read(),op[i].R=read();
p=read();
int L=0,R=n+100,ans=0;
while(L<=R)
{
int mid=(L+R)/2;
if(Check(mid)==true)
ans=max(ans,mid),L=mid+1;
else
R=mid-1;
}
printf("%d",ans);
return 0;
}
|
