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);
    }
}