传送门
解题思路
据说是经典思路：把多次排序转化成二分+01序列。
首先二分所求位置的数字是啥，将大于mid的数字变成1，将小于等于mid的数字变成0。
这样在排序的时候就相当于统计区间里的1的个数（区间和），然后区间全部变成0或者1。
也就是区间修改，区间求和，线段树可以实现。
AC代码
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
#include<ctime>
#include<stack>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!(c>='0'&&c<='9')) {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=1e5+5;
struct node{
int op,l,r;
}b[maxn];
int d[maxn*4],lazy[maxn*4],a0[maxn],a[maxn];
inline void pushup(int id){
d[id]=d[id*2]+d[id*2+1];
}
inline void pushdown(int id,int l,int r){
if(lazy[id]==-1) return;
lazy[id*2]=lazy[id*2+1]=lazy[id];
int mid=(l+r)/2;
d[id*2]=lazy[id]*(mid-l+1);
d[id*2+1]=lazy[id]*(r-mid);
lazy[id]=-1;
}
void add(int id,int l,int r,int x,int y,int v){
if(x>y) return;
if(x<=l&&r<=y){
lazy[id]=v;
d[id]=v*(r-l+1);
return;
}
pushdown(id,l,r);
int mid=(l+r)/2;
if(x<=mid) add(id*2,l,mid,x,y,v);
if(y>mid) add(id*2+1,mid+1,r,x,y,v);
pushup(id);
}
int query(int id,int l,int r,int x,int y){
if(x<=l&&r<=y) return d[id];
pushdown(id,l,r);
int mid=(l+r)/2;
int res=0;
if(x<=mid) res+=query(id*2,l,mid,x,y);
if(y>mid) res+=query(id*2+1,mid+1,r,x,y);
return res;
}
int main()
{
//ios::sync_with_stdio(false);
int n=read(),m=read();
for(int i=1;i<=n;i++) a0[i]=read();
for(int i=1;i<=m;i++){
b[i].op=read();
b[i].l=read();
b[i].r=read();
}
int q=read();
int l=1,r=n;
while(l<r){
memset(d,0,sizeof(d));
memset(lazy,-1,sizeof(lazy));
int mid=(l+r)/2;
for(int i=1;i<=n;i++) add(1,1,n,i,i,(a0[i]>mid));
for(int i=1;i<=m;i++){
int num=query(1,1,n,b[i].l,b[i].r);
if(b[i].op==1){
add(1,1,n,b[i].l,b[i].l+num-1,1);
add(1,1,n,b[i].l+num,b[i].r,0);
}else{
add(1,1,n,b[i].r-num+1,b[i].r,1);
add(1,1,n,b[i].l,b[i].r-num,0);
}
}
if(query(1,1,n,q,q)){
l=mid+1;
}else{
r=mid;
}
}
cout<<l<<endl;
return 0;
}