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
3 4 5 1 6 2
Sample Output
4 6 4 5 6 6
HINT
Source
Solution
预处理$[1, n]$中所有数的位置，每次把当前查找的数$x$旋到根上，其左儿子的子树大小就是答案。再对题意所述的区间加个reverse标记即可。
因为有区间加标记，所以最好加上头尾两个虚拟节点。
#include <bits/stdc++.h>
using namespace std;
struct spaly
{
int c[], fa, siz, rev;
}a[];
pair<int, int> b[]; void push_up(int k)
{
a[k].siz = a[a[k].c[]].siz + a[a[k].c[]].siz + ;
} void push_down(int k)
{
if(a[k].rev)
{
swap(a[k].c[], a[k].c[]), a[k].rev = ;
a[a[k].c[]].rev ^= , a[a[k].c[]].rev ^= ;
}
} void rotate(int &k, int x)
{
int y = a[x].fa, z = a[y].fa;
int dy = a[y].c[] == x, dz = a[z].c[] == y;
if(k == y) k = x, a[x].fa = z;
else a[z].c[dz] = x, a[x].fa = z;
a[y].c[dy] = a[x].c[!dy], a[a[x].c[!dy]].fa = y;
a[x].c[!dy] = y, a[y].fa = x;
push_up(y);
} void splay(int &k, int x)
{
while(k != x)
{
int y = a[x].fa, z = a[y].fa;
push_down(z), push_down(y), push_down(x);
if(k != y)
if(a[y].c[] == x ^ a[z].c[] == y) rotate(k, x);
else rotate(k, y);
rotate(k, x);
}
push_up(x);
} int find(int k, int x)
{
if(!k) return ;
push_down(k);
if(x <= a[a[k].c[]].siz) return find(a[k].c[], x);
if(x == a[a[k].c[]].siz + ) return k;
return find(a[k].c[], x - a[a[k].c[]].siz - );
} int main()
{
int n, root, pos;
while(~scanf("%d", &n) && n)
{
for(int i = ; i <= n; i++)
{
scanf("%d", &b[i].first);
b[i].second = i + ;
}
sort(b + , b + n + );
for(int i = ; i <= n + ; i++)
{
a[i].fa = i + , a[i].c[] = i - ;
a[i].siz = i, a[i].c[] = a[i].rev = ;
}
a[n + ].fa = , root = n + ;
for(int i = ; i <= n; i++)
{
splay(root, b[i].second);
pos = a[a[root].c[]].siz;
printf("%d", pos);
if(i != n) printf(" ");
splay(root, find(root, i));
splay(a[root].c[], find(root, pos + ));
a[a[a[root].c[]].c[]].rev ^= ;
}
puts("");
}
return ;
}
双倍经验的时候到了(｡･ω･)ﾉﾞBZOJ3506 我是雷锋我骄傲。