做了本题我的评价是：⭐⭐⭐⭐⭐
本题乍一看很怪，但是我们可以注意到它只查询一次，所以要从此考虑。
如果全暴力的话复杂度是 (O(nmlog(n))) 的。
所以我也不知道为什么就可以想到转换成 01 序列加二分答案处理，正确性略，复杂度：(O(nlog^2(n)))。
还是注意upd是别访问到了非法内存。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
template <class I>
inline void read(I &x){
int f=1;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c&15),c=getchar());
x*=f;
}
struct change{
int l,r;
bool op;
}q[N];
int n,m,a[N],Q,l=1,r,mid,ans;
struct tree{
int l,r,cnt,lazy;
#define l(x) t[x].l
#define r(x) t[x].r
#define mid(x) ((t[x].l+t[x].r)/2)
#define cnt(x) t[x].cnt
#define lazy(x) t[x].lazy
}t[4*N];
inline void upd(int p){
if(t[p].l==t[p].r) return;
cnt(p)=cnt(p*2)+cnt(p*2+1);
}
inline void pushdown(int p){
if(!lazy(p)||(t[p].l==t[p].r)) return;
lazy(p*2)=lazy(p*2+1)=lazy(p);
if(lazy(p)==1) {
cnt(p*2+1)=r(p*2+1)-l(p*2+1)+1;
cnt(p*2)=r(p*2)-l(p*2)+1;
}
else cnt(p*2+1)=cnt(p*2)=0;
lazy(p)=0;
}
void build(int p,int l,int r){
l(p)=l,r(p)=r,lazy(p)=0;
if(l==r){
cnt(p)=((a[l]>=mid)?1:0);
return;
}
build(p*2,l,mid(p));
build(p*2+1,mid(p)+1,r);
upd(p);
}
void change(int p,int o,int l,int r){
if(l(p)>=l&&r(p)<=r){
lazy(p)=((o==1)?1:-1);
cnt(p)=((o==1)?(r(p)-l(p)+1):0);
return;
}
pushdown(p);
if(mid(p)>=l) change(p*2,o,l,r);
if(mid(p)<r) change(p*2+1,o,l,r);
upd(p);
}
int query(int p,int l,int r){
if(l(p)>=l&&r(p)<=r)
return cnt(p);
int res=0;
pushdown(p);
if(mid(p)>=l) res+=query(p*2,l,r);
if(mid(p)<r) res+=query(p*2+1,l,r);
return res;
}
inline bool check(){
build(1,1,n);
for(int i=1;i<=m;i++){
int num=query(1,q[i].l,q[i].r);
if(q[i].op){
change(1,1,q[i].l,q[i].l+num-1);
change(1,0,q[i].l+num,q[i].r);
}
else {
change(1,1,q[i].r-num+1,q[i].r);
change(1,0,q[i].l,q[i].r-num);
}
}
return (ans=((query(1,Q,Q))?mid:ans))==mid;
}
int main(){
read(n),read(m);
r=n;
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=m;i++)
read(q[i].op),read(q[i].l),read(q[i].r);
read(Q);
while(l<=r){
mid=(l+r)>>1;
if(check()) l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
return 0;
}