看到这道题按照套路首先想到二分答案（即二分 \(q\) 位置上的数，记作 \(mid\)）。
再按照套路将大于 \(mid\) 的数字设为 \(1\)，将等于 \(mid\) 的数设为 \(2\)，小于 \(mid\) 的数字设为 \(0\)。
那么对于区间 \([l,r,0]\) 操作，应该先讲 \(0,1,2\) 的数量找出来，然后按照从小到大的顺序 \(0,2,1\) 进行区间赋值，并支持区间求和，这用线段树维护即可。而 \(opt=1\) 的情况也是同理。
现在考虑二分指针如何移动。首先，\(mid,pos\) 两者并不满足单调性，也就是说，\(mid\) 增大，位置不一定取得到后面，减小同理。这时便要从另一个角度思考问题。
如果 \(a_q\) 是 \(1\)，说明答案比当前数字大，我们将指针右移；\(a_q=2\)，说明答案正好是 \(mid\)；\(a_q=0\)，说明答案比当前数字小，将指针左移。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read() {
int sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=1e5+10;
int n,m,q;
int a[N];
int ql[N],qr[N],qt[N];
int tr[N<<2][3],tag[N<<2][3];
struct node {
int a0,a1,a2;
friend node operator + (node x,node y) {
return {x.a0+y.a0,x.a1+y.a1,x.a2+y.a2};
}
};
inline void pushup(int nd) {
for(int i=0;i<=2;i++) tr[nd][i]=tr[nd<<1][i]+tr[nd<<1|1][i];
}
inline void add(int nd,int l,int r,int a0,int a1,int a2) {
tr[nd][0]=tr[nd][1]=tr[nd][2]=0;
tag[nd][0]=tag[nd][1]=tag[nd][2]=0;
if(a0) {tr[nd][0]=r-l+1; tag[nd][0]=1;}
if(a1) {tr[nd][1]=r-l+1; tag[nd][1]=1;}
if(a2) {tr[nd][2]=r-l+1; tag[nd][2]=1;}
}
inline void pushdown(int nd,int l,int r) {
if(!tag[nd][0]&&!tag[nd][1]&&!tag[nd][2]) return ;
int mid=l+r>>1;
add(nd<<1,l,mid,tag[nd][0],tag[nd][1],tag[nd][2]);
add(nd<<1|1,mid+1,r,tag[nd][0],tag[nd][1],tag[nd][2]);
tag[nd][0]=tag[nd][1]=tag[nd][2]=0;
}
void change(int nd,int l,int r,int x,int y,int a0,int a1,int a2) {
if(l>y||r<x) return ;
if(x>y) return ;
if(l>=x&&r<=y) return add(nd,l,r,a0,a1,a2);
int mid=l+r>>1;
pushdown(nd,l,r);
change(nd<<1,l,mid,x,y,a0,a1,a2);
change(nd<<1|1,mid+1,r,x,y,a0,a1,a2);
pushup(nd);
}
node query(int nd,int l,int r,int x,int y) {
if(l>y||r<x) return {0,0,0};
if(l>=x&&r<=y) return {tr[nd][0],tr[nd][1],tr[nd][2]};
int mid=l+r>>1;
pushdown(nd,l,r);
return query(nd<<1,l,mid,x,y)+query(nd<<1|1,mid+1,r,x,y);
}
int ask(int nd,int l,int r,int p) {
if(l==r) {
if(tr[nd][0]) return 0;
if(tr[nd][1]) return 1;
if(tr[nd][2]) return 2;
}
int mid=l+r>>1;
pushdown(nd,l,r);
if(l<=p&&p<=mid) return ask(nd<<1,l,mid,p);
else return ask(nd<<1|1,mid+1,r,p);
}
int check(int x) {
memset(tr,0,sizeof(tr));
memset(tag,0,sizeof(tag));
for(int i=1;i<=n;i++) {
if(a[i]<x) change(1,1,n,i,i,1,0,0);
if(a[i]==x) change(1,1,n,i,i,0,0,1);
if(a[i]>x) change(1,1,n,i,i,0,1,0);
}
for(int i=1;i<=m;i++) {
node num=query(1,1,n,ql[i],qr[i]);
if(qt[i]==0) {
change(1,1,n,ql[i],ql[i]+num.a0-1,1,0,0);
change(1,1,n,ql[i]+num.a0,ql[i]+num.a0+num.a2-1,0,0,1);
change(1,1,n,ql[i]+num.a0+num.a2,qr[i],0,1,0);
}
else {
change(1,1,n,ql[i],ql[i]+num.a1-1,0,1,0);
change(1,1,n,ql[i]+num.a1,ql[i]+num.a1+num.a2-1,0,0,1);
change(1,1,n,ql[i]+num.a1+num.a2,qr[i],1,0,0);
}
}
return ask(1,1,n,q);
}
int main() {
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) {
qt[i]=read();
ql[i]=read();
qr[i]=read();
}
cin>>q;
int l=1,r=n;
while(l<=r) {
int mid=l+r>>1;
int k=check(mid);
if(k==1) l=mid+1;
if(k==2) {cout<<mid; return 0;}
if(k==0) r=mid-1;
}
return 0;
}