题面

这是一道非常巧妙的线段树的题

我们会发现维护\(1 \sim n\)的序列非常困难，但如果我们维护\(01\)序列的的顺序，就非常容易了

但是我们怎么能把这道题变成维护\(01\)序列的顺序呢？

这道题只会对一个位置的数进行询问

那么我们是不是可以二分枚举这个数是几？这样的话，大于等于这个数就是\(1\)，小于这个数就是\(0\)，维护\(01\)序列的顺序，最后查询第\(q\)个位置上如果是\(0\)说明比这个数小，是\(1\)说明大于等于这个数，很明显这是满足二分的单调性的

下面放代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc getchar
#define maxn 100005
using namespace std;

inline ll read(){
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}int n,m,k,l,r,ans,a[maxn];

struct ahaha{
    int v,lz;
}t[maxn<<2];
#define lc p<<1
#define rc p<<1|1
inline void pushup(int p){
    t[p].v=t[lc].v+t[rc].v;
}
inline void pushdown(int p,int l,int r){
    int m=l+r>>1,&lz=t[p].lz;
    t[lc].v=(m-l+1)*lz;t[lc].lz=lz;
    t[rc].v=(r-m)*lz;t[rc].lz=lz;
    lz=-1;
}
void build(int p,int l,int r,int z){
    t[p].lz=-1;
    if(l==r){t[p].v=a[l]>=z;return;}
    int m=l+r>>1;
    build(lc,l,m,z);build(rc,m+1,r,z);
    pushup(p);
}
void update(int p,int l,int r,int L,int R,int z){
    if(l>R||r<L)return;
    if(L<=l&&r<=R){t[p].v=(r-l+1)*z;t[p].lz=z;return;}
    int m=l+r>>1;if(~t[p].lz)pushdown(p,l,r);
    update(lc,l,m,L,R,z);update(rc,m+1,r,L,R,z);
    pushup(p);
}
int query(int p,int l,int r,int L,int R){
    if(l>R||r<L)return 0;
    if(L<=l&&r<=R)return t[p].v;
    int m=l+r>>1;if(~t[p].lz)pushdown(p,l,r);
    return query(lc,l,m,L,R)+query(rc,m+1,r,L,R);
}

struct ahaha1{
    int op,l,r;
}q[maxn];
inline int pan(int p){
    build(1,1,n,p);
    for(int i=1;i<=m;++i){
        int z=query(1,1,n,q[i].l,q[i].r);
        if(q[i].op){
            update(1,1,n,q[i].l,q[i].l+z-1,1);
            update(1,1,n,q[i].l+z,q[i].r,0);
        }
        else{
            update(1,1,n,q[i].l,q[i].r-z,0);
            update(1,1,n,q[i].r-z+1,q[i].r,1);
        }
    }
    return query(1,1,n,k,k);
}

int main(){
    n=read();m=read();r=n;l=1;
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=m;++i)
        q[i]={read(),read(),read()};
    k=read();
    while(l<=r){
        int mid=l+r>>1;
        if(pan(mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}