luogu P2824 [HEOI2016/TJOI2016]排序

题目描述

在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,m\leq 1000$

对于100%的数据，n,m\leq 10^5$

且始终$1\leq q\leq 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;

}

巴特西