题意：BC 76 div1 1004 有中文题面

然后奉上官方题解：

这是一道良心的基础数据结构题。

我们二分a[k]的值，假设当前是mid，然后把大于mid的数字标为1，不大于mid的数字标为0。然后对所有操作做完以后检查一下a[k]位置上是0还是1。

因为只有两种值，所以操作还是不难做的。只要用一个线段树，支持区间求和、区间赋值即可。

这样要排序一个区间时只要查询一下里面有几个1和几个0，然后把前半段赋值为0，后半段赋值为1即可（降序的话就是反过来）。

复杂度是O(mlog^2n)。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int N=1e5+5;int a[N],b[N],T,n,m,k;int sum[N<<2];int lz[N<<2];int pushup(int rt){   sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int l,int r){  if(lz[rt]!=-1){     int mid=(l+r)>>1;     sum[rt<<1]=lz[rt]*(mid-l+1);     sum[rt<<1|1]=lz[rt]*(r-mid);     lz[rt<<1]=lz[rt<<1|1]=lz[rt];     lz[rt]=-1;  }  }void build(int rt,int l,int r){   lz[rt]=-1;   if(l==r){      sum[rt]=b[l];      return;   }   int mid=(l+r)>>1;   build(rt<<1,l,mid);   build(rt<<1|1,mid+1,r);   pushup(rt); }void update(int rt,int l,int r,int x,int y,int t){     if(x<=l&&r<=y){        sum[rt]=t*(r-l+1);        lz[rt]=t;        return;     }     int mid=(l+r)>>1;     pushdown(rt,l,r);     if(x<=mid)update(rt<<1,l,mid,x,y,t);     if(y>mid)update(rt<<1|1,mid+1,r,x,y,t);     pushup(rt);}int query(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)return sum[rt];    int mid=(l+r)>>1;    pushdown(rt,l,r);    if(y<=mid)return query(rt<<1,l,mid,x,y);    else if(x>mid)return query(rt<<1|1,mid+1,r,x,y);    return query(rt<<1,l,mid,x,y)+query(rt<<1|1,mid+1,r,x,y);}struct op{  int x,y,t;}o[N];bool check(int x){  for(int i=1;i<=n;++i)    b[i]=a[i]>x?1:0;   build(1,1,n);   for(int i=1;i<=m;++i){     int tmp=query(1,1,n,o[i].x,o[i].y);     if(!o[i].t){       if(o[i].x<=o[i].y-tmp)update(1,1,n,o[i].x,o[i].y-tmp,0);       if(o[i].y-tmp+1<=o[i].y)update(1,1,n,o[i].y-tmp+1,o[i].y,1);     }     else{       if(o[i].x<=o[i].x+tmp-1)update(1,1,n,o[i].x,o[i].x+tmp-1,1);       if(o[i].x+tmp<=o[i].y)update(1,1,n,o[i].x+tmp,o[i].y,0);     }   }   return query(1,1,n,k,k)==1; }int main(){    scanf("%d",&T);    while(T--){      scanf("%d%d",&n,&m);      for(int i=1;i<=n;++i)       scanf("%d",&a[i]);      for(int i=1;i<=m;++i)       scanf("%d%d%d",&o[i].t,&o[i].x,&o[i].y);       scanf("%d",&k);        int l=1,r=n;       while(l
          
           >1;         if(check(mid))l=mid+1;         else r=mid;       }       printf("%d\n",(l+r)>>1);     }      return 0;}