这题的思路好清奇

因为只有一次查询，我们考虑二分这个值为多少

将原序列转化为一个$01$序列，如果原序列上的值大于$mid$则为$1$否则为$0$

那么排序就可以用线段树优化，设该区间内$1$的个数为$res$，如果是升序排序，只要把$[r-res+1,r]$区间全部变为$1$，$[l,r-res]$区间全部变为$0$即可，用线段树区间覆盖即可

那么只要最后查询$k$的位置上是否是$1$，如果是的话$ans=mid,l=mid+1$，否则$r=mid-1$

考虑为什么能这样二分。我们经过这样之后，如果最后位置$k$上为$1$，那么这肯定是一个大于等于$mid$的数，否则肯定是一个小于$mid$的数

然后差不多了

1 //minamoto 2 #include
     
       3 #include
      
        4 using namespace std; 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 6 char buf[1<<21],*p1=buf,*p2=buf; 7 inline int read(){ 8     #define num ch-'0' 9     char ch;bool flag=0;int res;10     while(!isdigit(ch=getc()))11     (ch=='-')&&(flag=true);12     for(res=num;isdigit(ch=getc());res=res*10+num);13     (flag)&&(res=-res);14     #undef num15     return res;16 }17 const int N=30005;18 struct Q{19     int op,l,r;20     Q(){}21     Q(int op,int l,int r):op(op),l(l),r(r){}22 }q[N];23 int n,m,st[N],val[N],tag[N<<2],sum[N<<2],k;24 inline void upd(int p){sum[p]=sum[p<<1]+sum[p<<1|1];}25 inline void pd(int p,int l,int r){26     if(~tag[p]){27         tag[p<<1]=tag[p<<1|1]=tag[p];28         sum[p<<1]=tag[p]*l,sum[p<<1|1]=tag[p]*r;29         tag[p]=-1;30     }31 }32 void build(int p,int l,int r){33     tag[p]=-1;34     if(l==r) return (void)(sum[p]=st[l]);35     int mid=(l+r)>>1;36     build(p<<1,l,mid),build(p<<1|1,mid+1,r);37     upd(p);38 }39 void update(int p,int l,int r,int ql,int qr,int val){40     if(ql<=l&&qr>=r) return (void)(sum[p]=val*(r-l+1),tag[p]=val);41     int mid=(l+r)>>1;42     pd(p,mid-l+1,r-mid);43     if(ql<=mid) update(p<<1,l,mid,ql,qr,val);44     if(qr>mid) update(p<<1|1,mid+1,r,ql,qr,val);45     upd(p);46 }47 int query(int p,int l,int r,int ql,int qr){48     if(ql<=l&&qr>=r) return sum[p];49     int mid=(l+r)>>1;50     pd(p,mid-l+1,r-mid);51     int res=0;52     if(ql<=mid) res+=query(p<<1,l,mid,ql,qr);53     if(qr>mid) res+=query(p<<1|1,mid+1,r,ql,qr);54     return res;55 }56 int check(int mid){57     for(int i=1;i<=n;++i)58     st[i]=val[i]>=mid?1:0;59     build(1,1,n);60     for(int i=1;i<=m;++i){61         int l=q[i].l,r=q[i].r;62         if(q[i].op==0){63             int res=query(1,1,n,l,r);64             update(1,1,n,r-res+1,r,1);65             update(1,1,n,l,r-res,0);66         }else{67             int res=query(1,1,n,l,r);68             update(1,1,n,l,l+res-1,1);69             update(1,1,n,l+res,r,0);70         }71     }72     return query(1,1,n,k,k);73 }74 int main(){75 //    freopen("testdata.in","r",stdin);76     n=read(),m=read();77     for(int i=1;i<=n;++i) val[i]=read();78     for(int i=1,op,l,r;i<=m;++i)79     op=read(),l=read(),r=read(),q[i]=Q(op,l,r);80     k=read();81     int l=1,r=n,ans=0;82     while(l<=r){83         int mid=(l+r)>>1;84         if(check(mid)) l=mid+1,ans=mid;else r=mid-1;85     }86     printf("%d\n",ans);87     return 0;88 }