题目描述
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
输入格式
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。第二行为n个整数，表示1到n的一个全排列。接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。最后输入一个整数q，q表示排序完之后询问的位置
输出格式
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
说明/提示
河北省选2016第一天第二题。
对于30%的数据，(n,mleq 1000)
对于100%的数据，n,mleq 10^5$
且始终(1leq qleq n)
二分+线段树
二分q上的答案
对于大于mid的数，全部改成1，其它则为0
排序操作看成是对01序列排序
即可转化成线段树的区间修改
每次询问区间上多少个1，按照排序规则对区间赋值
O(nlog(n)log(n))
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=3e5+10;
struct node{
int op,l,r;
}e[N*5];
int A[N],q;
int n,m,x;
#define ls (p<<1)
#define rs (p<<1|1)
struct E{
int l,r,sum;
int op;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
}tree[N];
inline void build(int p,int l,int r){
l(p)=l;r(p)=r;
if(l==r){
sum(p)= A[l]>=x;
tree[p].op=0;
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
sum(p)=sum(ls)+sum(rs);
tree[p].op=0;
}
inline void pushdown(int p){
if(tree[p].op==0)return;
sum(ls)=(r(ls)-l(ls)+1)*(tree[p].op-1);
sum(rs)=(r(rs)-l(rs)+1)*(tree[p].op-1);
tree[ls].op=tree[p].op;
tree[rs].op=tree[p].op;
tree[p].op=0;
}
inline void change(int p,int l,int r,int d){
if(l>r)return;
if(l<=l(p)&&r(p)<=r){
sum(p)=d*(r(p)-l(p)+1);
tree[p].op=d+1;
return;
}
if(l>r(p)||r<l(p))return;
pushdown(p);
int mid=(l(p)+r(p))>>1;
if(l<=mid)change(ls,l,r,d);
if(r>mid)change(rs,l,r,d);
sum(p)=sum(ls)+sum(rs);
}
inline int ask(int p,int l,int r){
if(l<=l(p)&&r(p)<=r)return sum(p);
if(l>r(p)||r<l(p))return 0;
pushdown(p);
int ans=0;
ans+=ask(ls,l,r);
ans+=ask(rs,l,r);
return ans;
}
inline bool check(){
build(1,1,n);
for(int i=1;i<=m;i++){
int op=e[i].op,l=e[i].l,r=e[i].r;
int sum=ask(1,l,r);
if(op){
if(sum>0)change(1,l,l+sum-1,1);
change(1,l+sum,r,0);
}else{
if(sum<(r-l+1))change(1,l,r-sum,0);
change(1,r-sum+1,r,1);
}
}
return ask(1,q,q);
}
int main(){
cin>>n>>m;
int Min=1e9,Max=0;
for(int i=1;i<=n;i++){
scanf("%d",&A[i]);
Max=max(Max,A[i]);
Min=min(Min,A[i]);
}
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].op,&e[i].l,&e[i].r);
cin>>q;
int l=Min,r=Max,ans=-1;
while(l<=r){
x=(l+r)>>1;
if(check()){
l=x+1;
ans=x;
}else{
r=x-1;
}
}
cout<<ans<<endl;
}