这是一道非常巧妙的线段树的题
我们会发现维护\(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;
}