二分值mid，然后把>=mid的赋值为1，其他赋值为0，每次排序就是算出区间内01的个数，然后分别把0和1放到连续的一段内，这些都可以用线段树来维护
二分的判断条件是操作完之后q位置上是否为1
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n,m,q,a[N],o[N],l[N],r[N];
struct xds
{
int l,r,s[2],lz;
}t[N<<2];
struct qwe
{
int s[2];
qwe(int s0=0,int s1=1)
{
s[0]=s0,s[1]=s1;
}
qwe operator + (const qwe &b) const
{
return qwe(s[0]+b.s[0],s[1]+b.s[1]);
}
};
int read()
{
int r=0,f=1;
char p=getchar();
while(p>'9'||p<'0')
{
if(p=='-')
f=-1;
p=getchar();
}
while(p>='0'&&p<='9')
{
r=r*10+p-48;
p=getchar();
}
return r*f;
}
void ud(int ro)
{
t[ro].s[0]=t[ro<<1].s[0]+t[ro<<1|1].s[0];
t[ro].s[1]=t[ro<<1].s[1]+t[ro<<1|1].s[1];
}
void pd(int ro)
{
if(t[ro].lz!=-1)
{
t[ro<<1].s[t[ro].lz]=t[ro<<1].r-t[ro<<1].l+1;
t[ro<<1].s[t[ro].lz^1]=0;
t[ro<<1].lz=t[ro].lz;
t[ro<<1|1].s[t[ro].lz]=t[ro<<1|1].r-t[ro<<1|1].l+1;
t[ro<<1|1].s[t[ro].lz^1]=0;
t[ro<<1|1].lz=t[ro].lz;
t[ro].lz=-1;
}
}
void build(int ro,int l,int r,int w)
{
t[ro].l=l,t[ro].r=r,t[ro].lz=-1;
if(l==r)
{
t[ro].s[a[l]>=w]=1;
t[ro].s[a[l]<w]=0;
return;
}
int mid=(l+r)>>1;
build(ro<<1,l,mid,w);
build(ro<<1|1,mid+1,r,w);
ud(ro);
}
void update(int ro,int l,int r,int v)
{
if(l>r)
return;
if(t[ro].l==l&&t[ro].r==r)
{
t[ro].s[v]=t[ro].r-t[ro].l+1;
t[ro].s[v^1]=0;
t[ro].lz=v;
return;
}
pd(ro);
int mid=(t[ro].l+t[ro].r)>>1;
if(r<=mid)
update(ro<<1,l,r,v);
else if(l>mid)
update(ro<<1|1,l,r,v);
else
update(ro<<1,l,mid,v),update(ro<<1|1,mid+1,r,v);
ud(ro);
}
qwe ques(int ro,int l,int r)
{
if(t[ro].l==l&&t[ro].r==r)
return qwe(t[ro].s[0],t[ro].s[1]);
pd(ro);
int mid=(t[ro].l+t[ro].r)>>1;
if(r<=mid)
return ques(ro<<1,l,r);
else if(l>mid)
return ques(ro<<1|1,l,r);
else
return ques(ro<<1,l,mid)+ques(ro<<1|1,mid+1,r);
}
bool ok(int w)
{
build(1,1,n,w);
for(int i=1;i<=m;i++)
{
qwe u=ques(1,l[i],r[i]);//cerr<<"OK"<<endl;
if(o[i]==0)
update(1,l[i],l[i]+u.s[0]-1,0),update(1,l[i]+u.s[0],r[i],1);
else
update(1,l[i],l[i]+u.s[1]-1,1),update(1,l[i]+u.s[1],r[i],0);
}
return ques(1,q,q).s[1];
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
o[i]=read(),l[i]=read(),r[i]=read();
q=read();
int l=1,r=n,ans=1;
while(l<=r)
{
int mid=(l+r)>>1;//cerr<<mid<<endl;
if(ok(mid))
l=mid+1,ans=mid;
else
r=mid-1;
}
printf("%d
",ans);
return 0;
}