题意：BC 76 div1 1004 有中文题面
然后奉上官方题解：
这是一道良心的基础数据结构题。
我们二分a[k]的值，假设当前是mid，然后把大于mid的数字标为1，不大于mid的数字标为0。然后对所有操作做完以后检查一下a[k]位置上是0还是1。
因为只有两种值，所以操作还是不难做的。只要用一个线段树，支持区间求和、区间赋值即可。
这样要排序一个区间时只要查询一下里面有几个1和几个0，然后把前半段赋值为0，后半段赋值为1即可（降序的话就是反过来）。
复杂度是O(mlog^2n)。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> 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<r){ int mid=(l+r)>>1; if(check(mid))l=mid+1; else r=mid; } printf("%d ",(l+r)>>1); } return 0; }