Description
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
Input
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1 <= n, m <= 10^5第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置, \(1 <= q <= n。1 <= n <= 10^5，1 <= m <= 10^5\)
Output
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
Sample Input
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3
Sample Output
5
首先发现一个性质，这个答案是可以二分的 这是为啥啊？
然后二分之后我们就可以把所有小于等于mid的数变成0，大于等于mid的数变成1，然后对区间排序就变成了分别赋值0和1，就变成区间修改操作了，于是可以用线段树维护出来，如果发现第k位上是0那么说明l可能可以变大，否则r必须变小
然后就直接二分维护就行了，注意modify的时候边界问题
#include<bits/stdc++.h>
using namespace std;
#define fu(a,b,c) for(int a=b;a<=c;++a)
#define N 100010
#define LD (t<<1)
#define RD (t<<1|1)
int a[N],b[N],n,m,k;
int l[N],r[N],typ[N];
int siz[N<<2],chg[N<<2];
void pushup(int t){siz[t]=siz[LD]+siz[RD];}
void pushdown(int t,int l,int r){
if(l==r)return;
if(chg[t]!=-1){
int mid=(l+r)>>1;
if(l<=mid)chg[LD]=chg[t],siz[LD]=(mid-l+1)*chg[t];
if(mid<r)chg[RD]=chg[t],siz[RD]=(r-mid)*chg[t];
chg[t]=-1;
}
}
void build(int t,int l,int r){
if(l>r)return;
chg[t]=-1;
if(l==r){siz[t]=b[l];return;}
int mid=(l+r)>>1;
build(LD,l,mid);
build(RD,mid+1,r);
pushup(t);
}
void modify(int t,int l,int r,int L,int R,int vl){
if(L>R)return;
if(L<=l&&r<=R){chg[t]=vl,siz[t]=(r-l+1)*vl;return;}
pushdown(t,l,r);
int mid=(l+r)>>1;
if(R<=mid)modify(LD,l,mid,L,R,vl);
else if(L>mid)modify(RD,mid+1,r,L,R,vl);
else modify(LD,l,mid,L,mid,vl),modify(RD,mid+1,r,mid+1,R,vl);
pushup(t);
}
int query(int t,int l,int r,int L,int R){
if(L<=l&&r<=R)return siz[t];
pushdown(t,l,r);
int mid=(l+r)>>1,ans=0;
if(R<=mid)ans=query(LD,l,mid,L,R);
else if(L>mid)ans=query(RD,mid+1,r,L,R);
else ans=query(LD,l,mid,L,mid)+query(RD,mid+1,r,mid+1,R);
pushup(t);
return ans;
}
bool check(int val){
fu(i,1,n)b[i]=(a[i]>=val);
build(1,1,n);
fu(i,1,m){
int s=query(1,1,n,l[i],r[i]);
if(typ[i]==0){
modify(1,1,n,l[i],r[i]-s,0);
modify(1,1,n,r[i]-s+1,r[i],1);
}else{
modify(1,1,n,l[i],l[i]+s-1,1);
modify(1,1,n,l[i]+s,r[i],0);
}
}
return query(1,1,n,k,k);
}
int main(){
scanf("%d%d",&n,&m);
fu(i,1,n)scanf("%d",&a[i]);
fu(i,1,m)scanf("%d%d%d",&typ[i],&l[i],&r[i]);
scanf("%d",&k);
int l=1,r=n,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d",ans);
return 0;
}