标签：using strong [1] query ace 姐姐 全排列 space pushd
题目描述
在2016年，佳媛姐姐喜欢上了数字序列。因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。这个难题是这样子的：给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种：1:(0,l,r)表示将区间[l,r]的数字升序排序2:(1,l,r)表示将区间[l,r]的数字降序排序最后询问第q位置上的数字。
输入输出格式
输入格式：
输入数据的第一行为两个整数n和m。n表示序列的长度，m表示局部排序的次数。1
输出格式：
输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。
（luogu数据，30000）
题解：
确实开始比较没有思路。
不像某JZOJ模拟题，可以线段树维护区间内每个字符的个数。
但是这一共30000个字符啊！！！没办法乖乖排序
发现，突破口是，最后只要知道q位置是什么就可以！
神仙思路：
我们二分一个q位置的值mid，把所有的小于的值的位置赋值为1，否则就是0
然后循环m，0/1排序就比较方便了。线段树，找到区间有多少个1，多少个0，把所有的0放左边，然后放1（降序的话反过来）
最后，如果q位置是1，那么ans=mid,r=mid-1;
如果q位置是0，那么l=mid+1
复杂度O(nlog^2n)
代码：
#include#define mid ((l+r)>>1)
using namespace std;
const int N=30000+4;
int a[N];
int b[N];
int n,m;
struct node{
int sum;
int ch;
}t[4*N];
int q[N][3];
int pos;
void pushdown(int x,int l,int r){
if(t[x].ch==-1) return;
t[x1].ch=t[x].ch;
t[x1|1].ch=t[x].ch;
t[x1].sum=t[x].ch*(mid-l+1);
t[x1|1].sum=t[x].ch*(r-mid);
t[x].ch=-1;
}
void build(int x,int l,int r){
if(l==r){
t[x].ch=-1;
t[x].sum=b[l];
return;
}
t[x].ch=-1;
build(x1,l,mid);
build(x1|1,mid+1,r);
t[x].sum=t[x1].sum+t[x1|1].sum;
}
int query(int x,int l,int r,int L,int R){
if(LR){
return t[x].sum;
}
pushdown(x,l,r);
int ret=0;
if(L1,l,mid,L,R);
if(mid1|1,mid+1,r,L,R);
return ret;
}
void chan(int x,int l,int r,int L,int R,int c){
if(LR){
t[x].ch=c;
t[x].sum=(r-l+1)*c;
return;
}
pushdown(x,l,r);
if(L1,l,mid,L,R,c);
if(mid1|1,mid+1,r,L,R,c);
t[x].sum=t[x1].sum+t[x1|1].sum;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i"%d",&a[i]);
for(int i=1;i){
scanf("%d%d%d",&q[i][0],&q[i][1],&q[i][2]);
}
scanf("%d",&pos);
int l=1,r=n;
int ans;
while(lr){
int MID=(l+r)>>1;
for(int i=1;i){
if(a[i]>=MID) b[i]=1;
else b[i]=0;
//cout
}//cout
build(1,1,n);
//cout
for(int i=1;i){
//cout
int sum1=query(1,1,n,q[i][1],q[i][2]);
int sum0=q[i][2]-q[i][1]+1-sum1;
//cout
if(q[i][0]){//down
chan(1,1,n,q[i][1],q[i][1]+sum1-1,1);
chan(1,1,n,q[i][1]+sum1,q[i][2],0);
}
else{//up
chan(1,1,n,q[i][1],q[i][1]+sum0-1,0);
chan(1,1,n,q[i][1]+sum0,q[i][2],1);
}
}
int lp=query(1,1,n,pos,pos);
if(lp==1) ans=MID,l=MID+1;
else r=MID-1;
}
printf("%d",ans);
return 0;
}
[HEOI2016/TJOI2016]排序
标签：using strong [1] query ace 姐姐 全排列 space pushd
原文地址：https://www.cnblogs.com/Miracevin/p/9601189.html