题目描述
输入
输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。
输出
输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。 注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。
样例输入
6
3 4 5 1 6 2
样例输出
4 6 4 5 6 6
题解
splay
先将原数据从小到大排序，类似于离散化，把它们的排名存入splay中。
那么第k小的数的数组下标就是k。
区间反转即可。
#include <cstdio>
#include <algorithm>
#define N 100005
using namespace std;
struct data
{
int num , pos;
}a[N];
int c[2][N] , fa[N] , tag[N] , si[N] , id[N] , root;
bool cmp(data a , data b)
{
return a.num == b.num ? a.pos < b.pos : a.num < b.num;
}
void pushup(int k)
{
si[k] = si[c[0][k]] + si[c[1][k]] + 1;
}
void pushdown(int k)
{
if(tag[k])
{
swap(c[0][c[0][k]] , c[1][c[0][k]]);
swap(c[0][c[1][k]] , c[1][c[1][k]]);
tag[c[0][k]] ^= 1;
tag[c[1][k]] ^= 1;
tag[k] = 0;
}
}
void build(int l , int r , int f)
{
if(l > r) return;
int mid = (l + r) >> 1;
build(l , mid - 1 , mid);
build(mid + 1 , r , mid);
fa[id[mid]] = id[f];
c[mid > f][id[f]] = id[mid];
pushup(id[mid]);
}
void rotate(int &k , int x)
{
int y = fa[x] , z = fa[y] , l , r;
l = (c[0][y] != x);
r = l ^ 1;
if(y == k) k = x;
else if(c[0][z] == y) c[0][z] = x;
else c[1][z] = x;
fa[x] = z;
fa[y] = x;
fa[c[r][x]] = y;
c[l][y] = c[r][x];
c[r][x] = y;
pushup(y);
pushup(x);
}
void splay(int &k , int x)
{
while(x != k)
{
int y = fa[x] , z = fa[y];
if(y != k)
{
if(c[0][y] == x ^ c[0][z] == y) rotate(k , x);
else rotate(k , y);
}
rotate(k , x);
}
}
int getrank(int x)
{
if(x == root) return si[c[0][x]] + 1;
int r = getrank(fa[x]);
pushdown(x);
if(x == c[0][fa[x]]) r -= si[c[1][x]] + 1;
else r += si[c[0][x]] + 1;
return r;
}
int find(int k , int x)
{
pushdown(k);
if(x <= si[c[0][k]]) return find(c[0][k] , x);
else if(x > si[c[0][k]] + 1) return find(c[1][k] , x - si[c[0][k]] - 1);
else return k;
}
int main()
{
int n , i;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ )
{
scanf("%d" , &a[i].num);
a[i].pos = i;
}
sort(a + 1 , a + n + 1 , cmp);
for(i = 1 ; i <= n ; i ++ )
id[a[i].pos + 1] = i;
id[1] = n + 1;
id[n + 2] = n + 2;
build(1 , n + 2 , 0);
root = id[(n + 3) >> 1];
for(i = 1 ; i <= n ; i ++ )
{
int ri = getrank(i) , tx , ty;
printf("%d%c" , ri - 1 , i == n ? '\n' : ' ');
tx = find(root , i);
ty = find(root , ri + 1);
splay(root , tx);
splay(c[1][root] , ty);
swap(c[0][c[0][c[1][root]]] , c[1][c[0][c[1][root]]]);
tag[c[0][c[1][root]]] ^= 1;
}
return 0;
}