Description
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
solution
在看到二分答案这个标签后就是SBT了
首先常规套路，如果值域较小，那么枚举值域线段树区间覆盖
那么这题这么做这个转换呢？直接二分答案，把小于的部分赋为0，大于等于部分1，这样转换过来了，注意线段树只要存1就好,0直接可以相减得出
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=100005;
#define ls (node<<1)
#define rs (node<<1|1)
int n,m,a[N],t[N<<2],L[N],R[N],op[N],mark[N<<2],P;
void upd(int node){t[node]=t[ls]+t[rs];}
il void pushdown(RG int node,int l,int r){
if(mark[node]==-1)return ;
int k=mark[node],mid=(l+r)>>1;
t[ls]=k*(mid-l+1);t[rs]=k*(r-mid);
mark[ls]=mark[rs]=k;mark[node]=-1;
}
il void build(int l,int r,RG int node,int li){
mark[node]=-1;t[node]=0;
if(l==r){t[node]=(a[l]>=li);return ;}
int mid=(l+r)>>1;
build(l,mid,ls,li);build(mid+1,r,rs,li);
upd(node);
}
il int query(int l,int r,RG int node,int sa,int se){
if(l>se || r<sa)return 0;
if(sa<=l && r<=se)return t[node];
pushdown(node,l,r);
int mid=(l+r)>>1;
int q1=query(l,mid,ls,sa,se);
int q2=query(mid+1,r,rs,sa,se);
return q1+q2;
}
il void updata(int l,int r,RG int node,int sa,int se,int i){
if(l>se || r<sa)return ;
if(sa<=l && r<=se){
t[node]=i*(r-l+1);mark[node]=i;
return ;
}
pushdown(node,l,r);
int mid=(l+r)>>1;
updata(l,mid,ls,sa,se,i);updata(mid+1,r,rs,sa,se,i);
upd(node);
}
bool check(int mid){
build(1,n,1,mid);
int l,r,re[2];
for(int i=1;i<=m;i++){
l=L[i];r=R[i];
re[1]=query(1,n,1,l,r);
re[0]=r-l+1-re[1];
if(op[i]){
updata(1,n,1,l,l+re[1]-1,1);
updata(1,n,1,l+re[1],r,0);
}
else{
updata(1,n,1,l,l+re[0]-1,0);
updata(1,n,1,l+re[0],r,1);
}
}
return query(1,n,1,P,P);
}
void work()
{
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",&op[i],&L[i],&R[i]);
int l=1,r=n,mid,ans;scanf("%d",&P);
while(l<=r){
mid=(l+r)>>1;
if(check(mid))ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
int main()
{
work();
return 0;
}