题目描述
输入
输入共两行，第一行为一个整数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#include #define N 100005using 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;}