经验还是不够……
原题：
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题
，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排
序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q
位置上的数字。
1 <= n, m <= 10^5
没思路，看题解
这个本应不看题解的，但是急于刷AC数就看了，果然还是要放下每日6题的任务？
正解是二分一个值，把序列中<=它的设为1，大于的设为0，然后建线段树
每次排序先查询区间中有多少个1，然后以1的个数为分界线，根据升序或降序把左边和右边分别buff成1或0
这样一番操作之后第x的位置的值就表示位置x上的数和当前二分的数的大小关系
然后根据这个二分就行了
暂时不能把这个方法延伸到更多的地方去，需要再思考
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int oo=;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct dcd{int mk,x,y;}b[];
int n,m,a[],qst;
int v[],dt[];
int mn=oo,mx=;
void gtsgmttr(int x,int y,int l,int r){
dt[x]=-,v[x]=;
if(l==r){ v[x]=(y>=a[l]); return ;}
int md=(l+r)>>;
gtsgmttr(x<<,y,l,md),gtsgmttr(x<<|,y,md+,r);
v[x]=v[x<<]+v[x<<|];
}
void pshd(int x,int l,int r,int md){
if(dt[x]==-) return ;
v[x<<]=(md-l+)*dt[x],v[x<<|]=(r-md)*dt[x];
dt[x<<]=dt[x<<|]=dt[x];
dt[x]=-;
}
void mdf(int x,int l,int r,int z,int ll,int rr){
if(l>r) return ;
if(l==ll && r==rr){ v[x]=(r-l+)*z,dt[x]=z; return ;}
int md=(ll+rr)>>; pshd(x,ll,rr,md);
if(l<=md && r>md) mdf(x<<,l,md,z,ll,md),mdf(x<<|,md+,r,z,md+,rr);
else if(r<=md) mdf(x<<,l,r,z,ll,md);
else mdf(x<<|,l,r,z,md+,rr);
v[x]=v[x<<]+v[x<<|];
}
int qr(int x,int l,int r,int ll,int rr){
if(l==ll && r==rr) return v[x];
int md=(ll+rr)>>; pshd(x,ll,rr,md);
if(l<=md && r>md) return qr(x<<,l,md,ll,md)+qr(x<<|,md+,r,md+,rr);
else if(r<=md) return qr(x<<,l,r,ll,md);
else return qr(x<<|,l,r,md+,rr);
}
int sch(int x,int y,int ll,int rr){
if(y==ll && y==rr) return v[x];
int md=(ll+rr)>>; pshd(x,ll,rr,md);
if(y<=md) return sch(x<<,y,ll,md);
else return sch(x<<|,y,md+,rr);
}
bool chck(int x){
gtsgmttr(,x,,n);
//cout<<x<<endl;
//for(int i=1;i<=n;++i) printf("%d ",sch(1,i,1,n));
//cout<<endl;
int bwl;
for(int i=;i<=m;++i){
bwl=qr(,b[i].x,b[i].y,,n);
/*if(b[i].mk) mdf(1,b[i].x,b[i].x+bwl-1,0,1,n),mdf(1,b[i].x+bwl,b[i].y,1,1,n);
else mdf(1,b[i].x,b[i].y-bwl,1,1,n),mdf(1,b[i].y-bwl+1,b[i].y,0,1,n);*/
if(b[i].mk) mdf(,b[i].x,b[i].y-bwl,,,n),mdf(,b[i].y-bwl+,b[i].y,,,n);
else mdf(,b[i].x,b[i].x+bwl-,,,n),mdf(,b[i].x+bwl,b[i].y,,,n);
//for(int j=1;j<=n;++j) printf("%d ",sch(1,j,1,n));
//cout<<endl;
}
return sch(,qst,,n);
}
int bnrsch(){
int l=mn,r=mx,md;
while(l+<r) md=(l+r)>>,(chck(md) ? r : l)=md;
return chck(l) ? l : r;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m;
for(int i=;i<=n;++i) a[i]=rd(),mn=min(mn,a[i]),mx=max(mx,a[i]);
for(int i=;i<=m;++i) b[i].mk=rd(),b[i].x=rd(),b[i].y=rd();
cin>>qst;
cout<<bnrsch()<<endl;
return ;
}