Description
给出一个$1$到$n$的全排列,现在对这个全排列序列进行$m$次局部排序,排序分为$2$种：
$1.(0,l,r)$表示将区间$[l,r]$的数字升序排序;
$2.(1,l,r)$表示将区间$[l,r]$的数字降序排序.
最后询问第$q$位置上的数字.
Input
第$1$行为两个整数$n$和$m$.$n$表示序列的长度,$m$表示局部排序的次数.
第$2$行为$n$个整数,表示$1$到$n$的一个全排列.
接下来输入$m$行,每$1$行有$3$个整数$op,l,r$.
$op$为$0$代表升序排序,$op$为$1$代表降序排序;$l,r$表示排序的区间.
最后输入一个整数$q$,$q$表示排序完之后询问的位置.
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
HINT
$1\;\leq\;n,m\;\leq\;10^5,1\;\leq\;q\;\leq\;n.$
Solution
二分答案$ans$.
把$\;\leq\;ans$的位置标为$1$,其余标为$0$.
线段树维护排序操作,最后判断位置$q$上是否为$0$.
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100005
#define M 300005
using namespace std;
struct linetree{
int l,r,t,op;
}lt[M];
struct quest{
int op,l,r;
}b[N];
int a[N],n,m,q,t,l,r,mid;
inline void build(int u,int l,int r,int k){
lt[u].l=l;lt[u].r=r;lt[u].op=0;
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
build(lef,l,mid,k);build(rig,mid+1,r,k);
lt[u].t=lt[lef].t+lt[rig].t;
}
else if(a[lt[u].l]>=k) lt[u].t=0;
else lt[u].t=1;
}
inline void cover(int u,int i){
if(lt[u].l>=b[i].l&<[u].r<=b[i].r){
if(!b[i].op){
lt[u].op=-1;
if(lt[u].l-b[i].l+1<=t){
lt[u].t=min(t-(lt[u].l-b[i].l),lt[u].r-lt[u].l+1);
}
else lt[u].t=0;
}
else{
lt[u].op=1;
if(b[i].r-lt[u].r+1<=t){
lt[u].t=min(t-(b[i].r-lt[u].r),lt[u].r-lt[u].l+1);
}
else lt[u].t=0;
}
}
else if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1;
int mid=(lt[u].l+lt[u].r)>>1;
if(lt[u].op>0)/*降序*/{
lt[u].op=0;lt[lef].op=lt[rig].op=1;
lt[rig].t=min(lt[u].t,lt[rig].r-lt[rig].l+1);
lt[lef].t=lt[u].t-lt[rig].t;
}
else if(lt[u].op<0)/*升序*/{
lt[u].op=0;lt[lef].op=lt[rig].op=-1;
lt[lef].t=min(lt[u].t,lt[lef].r-lt[lef].l+1);
lt[rig].t=lt[u].t-lt[lef].t;
}
if(b[i].l<=mid) cover(lef,i);
if(b[i].r>mid) cover(rig,i);
lt[u].t=lt[lef].t+lt[rig].t;
}
}
inline int ask(int u,int l,int r){
if(lt[u].l>=l&<[u].r<=r)
return lt[u].t;
if(lt[u].l<lt[u].r){
int lef=u<<1,rig=u<<1|1,ret=0;
int mid=(lt[u].l+lt[u].r)>>1;
if(lt[u].op>0)/*降序*/{
lt[u].op=0;lt[lef].op=lt[rig].op=1;
lt[rig].t=min(lt[u].t,lt[rig].r-lt[rig].l+1);
lt[lef].t=lt[u].t-lt[rig].t;
}
else if(lt[u].op<0)/*升序*/{
lt[u].op=0;lt[lef].op=lt[rig].op=-1;
lt[lef].t=min(lt[u].t,lt[lef].r-lt[lef].l+1);
lt[rig].t=lt[u].t-lt[lef].t;
}
if(l<=mid) ret+=ask(lef,l,r);
if(r>mid) ret+=ask(rig,l,r);
return ret;
}
}
inline bool chk(int k){
build(1,1,n,k);
for(int i=1;i<=m;++i){
t=ask(1,b[i].l,b[i].r);cover(1,i);
}
return !ask(1,q,q);
}
inline void init(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<=m;++i)
scanf("%d%d%d",&b[i].op,&b[i].l,&b[i].r);
scanf("%d",&q);
l=1;r=n;
while(l<r){
mid=(l+r+1)>>1;
if(chk(mid)) l=mid;
else r=mid-1;
}
printf("%d\n",l);
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
init();
fclose(stdin);
fclose(stdout);
return 0;
}