用了离线01线段树+二分的做法

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,q,a[100005],ty[100005],l[100005],r[100005],ans;
struct O{
    int l,r,sum,lazy;
    int len(){return r-l+1;}
}o[400005];
void build(int it,int l,int r,int std){
    o[it].l=l,o[it].r=r,o[it].lazy=0;
    if(l==r){
        o[it].sum=a[l]>=std;
        return;
    }
    int mid=l+r>>1;
    build(it<<1,l,mid,std);
    build(it<<1|1,mid+1,r,std);
    o[it].sum=o[it<<1].sum+o[it<<1|1].sum;
}
void push(int it){
	if(o[it].lazy==0)return;
    if(o[it].lazy==1)
        o[it<<1].sum=o[it<<1].len(),
        o[it<<1|1].sum=o[it<<1|1].len();
    else
        o[it<<1].sum=o[it<<1|1].sum=0;
    o[it<<1].lazy=o[it<<1|1].lazy=o[it].lazy;
    o[it].lazy=0;
}
void update(int it,int l,int r,int x){
    if(o[it].l==l&&o[it].r==r){
        o[it].sum=x*o[it].len();
        o[it].lazy=(x==1?1:-1);
        return;
    }
    push(it);
    int mid=o[it].l+o[it].r>>1;
    if(mid>=r)update(it<<1,l,r,x);
    else if(mid<l)update(it<<1|1,l,r,x);
    else update(it<<1,l,mid,x),update(it<<1|1,mid+1,r,x);
    o[it].sum=o[it<<1].sum+o[it<<1|1].sum;
}
int query(int it,int l,int r){
    if(o[it].l==l&&o[it].r==r)return o[it].sum;
    push(it);
    int mid=o[it].l+o[it].r>>1;
    if(mid>=r)return query(it<<1,l,r);
    else if(mid<l)return query(it<<1|1,l,r);
    else return query(it<<1,l,mid)+query(it<<1|1,mid+1,r);
}
int query2(int it,int to){
    if(o[it].l==to&&o[it].r==to)return o[it].sum;
    push(it);
    int mid=o[it].l+o[it].r>>1;
    if(to<=mid)query2(it<<1,to);
    else query2(it<<1|1,to);
}
bool check(int std){
    build(1,1,n,std);
    for(int i=1;i<=m;i++){
        int cnt=query(1,l[i],r[i]);
		if(cnt==0||cnt==r[i]-l[i]+1)continue;
        else if(ty[i]==0){
            update(1,l[i],r[i]-cnt,0);
            update(1,r[i]-cnt+1,r[i],1);
        }else{
            update(1,l[i],l[i]+cnt-1,1);
            update(1,l[i]+cnt,r[i],0);
        }
    }
	return query2(1,q);
}
signed main(){
	freopen("in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&ty[i],&l[i],&r[i]);
    cin>>q;
    int L=1,R=n;
    while(L<=R){
        int mid=L+R>>1,tf=check(mid);
		if(tf==1)
            L=mid+1,ans=mid;
        else R=mid-1;
    }
    cout<<ans;
}