【题意概述】
对一个1到n的排列做m次区间排序，最后询问位置q上面的数。
【题解】
区间排序的效率是nlogn，所以暴力做的话效率是mnlogn，显然达不到要求。
我们考虑二分答案。如果某个位置的数比mid小，就设为0，如果么某个位置的数大于等于mid，就设为1. check的时候我们只需对01序列排序就好了，这个可以用线段树做到logn.
如果排序后位置q的数为1，那么就表示原来这里的数大于等于mid，所以我们要挪动l，否则挪动r.
总的时间复杂度为m*logn*logn
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define N 30010
#define ls (u<<1)
#define rs (u<<1|1)
#define len(x) (a[x].r-a[x].l+1)
using namespace std;
int n,m,v[N],l,r,mid,pos;
struct tree{
int l,r,c0,c1,num; bool same;
}a[N<<];
struct opt{
int l,r,type;
}b[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
void build(int u,int l,int r){
a[u].l=l; a[u].r=r; a[u].same=; a[u].c0=a[u].c1=;
if(l<r){
int mid=(l+r)>>;
build(ls,l,mid); build(rs,mid+,r);
a[u].c0=a[ls].c0+a[rs].c0; a[u].c1=a[ls].c1+a[rs].c1;
}
else{
if(v[l]>=mid) a[u].c1=,a[u].c0=;
else a[u].c0=,a[u].c1=;
}
}
inline void pushdown(int u){
a[u].same=; a[ls].same=a[rs].same=;
a[ls].num=a[rs].num=a[u].num;
if(!a[u].num) a[ls].c0=len(ls),a[ls].c1=,a[rs].c0=len(rs),a[rs].c1=;
else a[ls].c0=,a[ls].c1=len(ls),a[rs].c0=,a[rs].c1=len(rs);
}
void update(int u,int l,int r,int num){
if(l<=a[u].l&&a[u].r<=r){
a[u].same=; a[u].num=num;
if(num==) a[u].c1=len(u),a[u].c0=;
else a[u].c0=len(u),a[u].c1=;
return;
}
if(a[u].same) pushdown(u);
int mid=(a[u].l+a[u].r)>>;
if(l<=mid) update(ls,l,r,num);
if(r>mid) update(rs,l,r,num);
a[u].c0=a[ls].c0+a[rs].c0;
a[u].c1=a[ls].c1+a[rs].c1;
}
int query0(int u,int l,int r){
if(l<=a[u].l&&a[u].r<=r) return a[u].c0;
if(a[u].same) pushdown(u);
int mid=(a[u].l+a[u].r)>>,ret=;
if(l<=mid) ret=query0(ls,l,r);
if(r>mid) ret+=query0(rs,l,r);
return ret;
}
int query1(int u,int l,int r){
if(l<=a[u].l&&a[u].r<=r) return a[u].c1;
if(a[u].same) pushdown(u);
int mid=(a[u].l+a[u].r)>>,ret=;
if(l<=mid) ret=query1(ls,l,r);
if(r>mid) ret+=query1(rs,l,r);
return ret;
}
inline bool check(){
build(,,n); int r0=,r1=;
for(rg int i=;i<=m;i++){
r0=query0(,b[i].l,b[i].r); r1=query1(,b[i].l,b[i].r);
if(b[i].type==) update(,b[i].l,b[i].l+r0-,),update(,b[i].l+r0,b[i].r,);
else update(,b[i].l,b[i].l+r1-,),update(,b[i].l+r1,b[i].r,);
}
r0=query0(,pos,pos); r1=query1(,pos,pos);
return r1>;
}
int main(){
n=read(); m=read();
for(rg int i=;i<=n;i++) v[i]=read();
for(rg int i=;i<=m;i++) b[i].type=read(),b[i].l=read(),b[i].r=read();
pos=read();
l=,r=n+;
while(l+<r){
mid=(l+r)>>;
if(check()) l=mid; else r=mid;
}
printf("%d\n",l);
}