Description
Input
输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000。
第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号。
Output
输出共一行,N个用空格隔开的正整数P1,P2,P3…Pn,Pi表示第i次操作前第i小的物品所在的位置。
注意:如果第i次操作前,第i小的物品己经在正确的位置Pi上,我们将区间[Pi,Pi]反转(单个物品)。
Sample Input
6
3 4 5 1 6 2
Sample Output
4 6 4 5 6 6
题目分析
spaly 裸题 题目让你干什么就干什么
查询rank时同时维护标记有两种方法 递归或者用栈都行
注意递归时要pushdown(root)
#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[301000*3],size[301000*3],key[301000*3],lson[301000*3],rson[301000*3];
int lazy[301000*3],fa[301000*3];
int tot,root;
void update(int x)
{
size[x]=size[lson[x]]+size[rson[x]]+1;
}
void pushdown(int x)
{
if(lazy[x])
{
swap(lson[x],rson[x]);
if(lson[x]) lazy[lson[x]]^=1;
if(rson[x]) lazy[rson[x]]^=1;
lazy[x]=0;
}
}
int merge(int x,int y)
{
pushdown(x),pushdown(y);
if(x==0||y==0) return x|y;
if(key[x]<key[y])
{
lson[y]=merge(x,lson[y]),fa[lson[y]]=y,update(y);
return y;
}
rson[x]=merge(rson[x],y),fa[rson[x]]=x,update(x);
return x;
}
par split(int x,int k)
{
if(k==0) return make_pair(0,x);
pushdown(x);
int l=lson[x],r=rson[x];
if(k==size[lson[x]])
{
lson[x]=0,update(x),fa[lson[x]]=0;
return make_pair(l,x);
}
if(k==size[lson[x]]+1)
{
rson[x]=0,update(x),fa[rson[x]]=0;
return make_pair(x,r);
}
par t;
if(k<size[lson[x]])
{
t=split(l,k);
lson[x]=t.second,fa[lson[x]]=x,update(x);
return make_pair(t.first,x);
}
else
{
t=split(r,k-size[lson[x]]-1);
rson[x]=t.first,fa[rson[x]]=x,update(x);
return make_pair(x,t.second);
}
}
int getrank(int x)
{
if(x==root)
{
pushdown(root);
return size[lson[x]]+1;
}
int r=getrank(fa[x]);
pushdown(x);
if(x==lson[fa[x]]) r-=size[rson[x]]+1;
else r+=size[lson[x]]+1;
return r;
}
int find(int k,int x)
{
pushdown(k);
if(x<size[lson[k]]) return find(lson[k],x);
else if(x>size[lson[k]]+1) return find(rson[k],x-size[lson[k]]-1);
}
struct your
{
int num,v;
}a[300010];
int cmp(your j,your k)
{
if(j.v==k.v) return j.num<k.num;
return j.v<k.v;
}
int cmp2(your j,your k)
{
return j.num<k.num;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i].v),a[i].num=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++) a[i].v=i;
sort(a+1,a+n+1,cmp2);
for(int i=1;i<=n;i++) size[a[i].v]=1,key[a[i].v]=rand()*rand(),root=merge(root,a[i].v);
for(int i=1;i<=n;i++)
{
int ri=getrank(i);
printf("%d",ri);
if(i==n) putchar('\n');
else putchar(' ');
int tx=i;
int ty=ri;
if(tx>ty) swap(tx,ty);
par t1,t2;
t2=split(root,ty);
t1=split(t2.first,tx-1);
lazy[t1.second]^=1;
root=merge(merge(t1.first,t1.second),t2.second);
}
}