很巧妙的一个题
直接排序肯定会\(T\)飞
我们发现问题只有一个：第\(q\)个位置上的数字
不难想到从这里入手，二分答案，考虑第\(q\)个位置上的数字是什么，不妨设他为\(x\)
然后把大于等于\(x\)的数变成\(1\)，小于\(x\)的数变为\(0\)，把他转换为一个\(01\)排序问题：
对于区间\([l,r]\)的排序，我们找到\([l,r]\)中有多少个\(1\)，记为\(cnt_1\)，同理记\(cnt_0\)为区间中\(0\)的个数，若其为升序，则令\([l,cnt_0+l-1]\)变为\(0\)，\([r-cnt_1+1,r]\)变为\(1\)，降序同理，令\([l,cnt_1+l-1]\)变为\(1\)，\([r-cnt_0+1,r]\)变为\(0\)。
这样就变成了线段树基操：区间修改，区间查询
时间复杂度：
二分答案\(O(\log n)\)，一次修改\(O(\log n)\)，要修改\(m\)次\(O(m)\)，再加上每次二分答案前初始化\(O(n\log n)\)
总共就是\(O((n+m)\log_2^2 n)\)，可以接受
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50;
ll n,m,q,a[N],b[N];
ll op[N],l[N],r[N];
ll tr[N*16],tag[N*16],cnt0,cnt1;
void BT(ll wz,ll l,ll r)
{
if(l==r)
{
tr[wz]=b[l];
tag[wz]=-1;
return ;
}
ll mid=(l+r)/2;
BT(wz*2,l,mid);
BT(wz*2+1,mid+1,r);
tr[wz]=tr[wz*2]+tr[wz*2+1];
tag[wz]=-1;
}
void pushdown(ll wz,ll l,ll r)
{
ll mid=(l+r)/2;
tr[wz*2]=(mid-l+1)*tag[wz];
tr[wz*2+1]=(r-mid)*tag[wz];
tag[wz*2]=tag[wz];
tag[wz*2+1]=tag[wz];
tag[wz]=-1;
}
ll query(ll wz,ll l,ll r,ll le,ll ri)
{
if(le<=l&&ri>=r) return tr[wz];
if(tag[wz]!=-1) pushdown(wz,l,r);
ll mid=(l+r)/2,re=0;
if(le<=mid) re+=query(wz*2,l,mid,le,ri);
if(ri>mid) re+=query(wz*2+1,mid+1,r,le,ri);
return re;
}
void gai(ll wz,ll l,ll r,ll le,ll ri,ll x)
{
if(le<=l&&ri>=r)
{
tr[wz]=(r-l+1)*x;
tag[wz]=x;
return ;
}
if(tag[wz]!=-1) pushdown(wz,l,r);
ll mid=(l+r)/2;
if(le<=mid) gai(wz*2,l,mid,le,ri,x);
if(ri>mid) gai(wz*2+1,mid+1,r,le,ri,x);
tr[wz]=tr[wz*2]+tr[wz*2+1];
}
bool check(ll x)
{
for(ll i=1;i<=n;i++)
if(a[i]<x) b[i]=0;
else b[i]=1;
BT(1,1,n);
for(ll i=1;i<=m;i++)
{
cnt1=query(1,1,n,l[i],r[i]);
cnt0=r[i]-l[i]+1-cnt1;
if(op[i]==0)
{
if(cnt0!=0) gai(1,1,n,l[i],l[i]+cnt0-1,0);
if(cnt1!=0) gai(1,1,n,r[i]-cnt1+1,r[i],1);
}
if(op[i]==1)
{
if(cnt1!=0) gai(1,1,n,l[i],l[i]+cnt1-1,1);
if(cnt0!=0) gai(1,1,n,r[i]-cnt0+1,r[i],0);
}
}
ll re=query(1,1,n,q,q);
if(re==1) return true;
return false;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<=m;i++)
scanf("%lld %lld %lld",&op[i],&l[i],&r[i]);
scanf("%lld",&q);
ll l=1,r=n,mid;
while(l<r)
{
mid=(l+r+1)/2;
if(check(mid)) l=mid;
else r=mid-1;
}
printf("%lld\n",l);
return 0;
}