思路：
二分线段树；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
#define maxtree maxn<<2
int val[maxtree],L[maxtree],R[maxtree],mid[maxtree];
int len[maxtree],tag[maxtree],n,ai[maxn],bi[maxn];
int op[maxn],ql[maxn],qr[maxn],q,m;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void build(int now,int l,int r)
{
L[now]=l,R[now]=r,len[now]=r-l+,tag[now]=;
if(l==r)
{
val[now]=bi[l];
return;
}
mid[now]=l+r>>,build(now<<,l,mid[now]);
build(now<<|,mid[now]+,r),val[now]=val[now<<]+val[now<<|];
}
void pushdown(int now)
{
if(tag[now]==)
{
tag[now<<]=,tag[now<<|]=;
val[now<<]=,val[now<<|]=;
}
else
{
tag[now<<]=,tag[now<<|]=;
val[now<<]=len[now<<],val[now<<|]=len[now<<|];
}
tag[now]=;
}
void change(int now,int l,int r,int x)
{
if(L[now]>=l&&R[now]<=r)
{
tag[now]=x;
if(x==) val[now]=;
else val[now]=len[now];
return;
}
if(tag[now]) pushdown(now);
if(l<=mid[now]) change(now<<,l,r,x);
if(r>mid[now]) change(now<<|,l,r,x);
val[now]=val[now<<]+val[now<<|];
}
int query(int now,int l,int r)
{
if(L[now]>=l&&R[now]<=r) return val[now];
if(tag[now]) pushdown(now);int res=;
if(l<=mid[now]) res+=query(now<<,l,r);
if(r>mid[now]) res+=query(now<<|,l,r);
return res;
}
bool check(int x)
{
for(int i=;i<=n;i++) bi[i]=(ai[i]>=x);
build(,,n);int tmp;
for(int i=;i<=m;i++)
{
tmp=query(,ql[i],qr[i]);
if(!op[i])
{
if(tmp!=qr[i]-ql[i]+&&tmp) change(,ql[i],qr[i]-tmp,),change(,qr[i]-tmp+,qr[i],);
else if(tmp==qr[i]-ql[i]+) change(,ql[i],qr[i],);
else change(,ql[i],qr[i],);
}
else
{
if(tmp!=qr[i]-ql[i]+&&tmp) change(,ql[i],ql[i]+tmp-,),change(,ql[i]+tmp,qr[i],);
else if(tmp==qr[i]-ql[i]+) change(,ql[i],qr[i],);
else change(,ql[i],qr[i],);
}
}
return query(,q,q);
}
int main()
{
in(n),in(m);
for(int i=;i<=n;i++) in(ai[i]);
for(int i=;i<=m;i++) in(op[i]),in(ql[i]),in(qr[i]);
int l=,r=n,mid,ans;in(q);
while(l<=r)
{
mid=l+r>>;
if(check(mid)) l=mid+,ans=mid;
else r=mid-;
}
cout<<ans;
return ;
}