http://acm.hdu.edu.cn/showproblem.php?pid=1890
题意：有一个无序序列，经过不断地翻转，使得最后的序列是一个升序的序列，而且如果相同数字要使在原本序列靠前的在前面。对于每一个位置，输出于哪个位置翻转。
思路：想通了之后其实挺简单的，不过挺巧妙。一开始先记录每一个位的pos，并对数组升序排序，然后我们从小到大枚举数组里的元素，对于每个元素，我们可以知道：i 就是翻转后应当在序列中的位置，a[i].pos就是它在原序列的位置。这个时候，我们只要在建树的时候利用中序遍历就是原数组的样子的性质，让节点的值就是它在原数组的位置，即建一个新的节点的时候，x 就是在原数组中的编号，例如样例：3 4 5 1 6 2，那么对应的节点的值就是 1 2 3 4 5 6 了。然后对于每一个询问，我们知道了它在原序列的位置，我们将它的位置（即节点本身的值）旋转到根节点，那么它的左子树的 sz 就是它目前所在的位置（因为一开始多了一个节点），然后再对 目标位置 和 所在的位置进行区间翻转，就可以完成了。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
#define INF 0x7fffffff
#define lson ch[x][0]
#define rson ch[x][1]
#define keytree ch[ch[root][1]][0]
#define rootkey ch[root][1]
#define N 300000
struct node
{
int val, id;
}a[N];
struct SplayTree {
int num[N], sz[N], fa[N], ch[N][], root, rev[N];
int n; void PushUp(int x) {
sz[x] = sz[lson] + sz[rson] + ;
} void PushDown(int x) {
if(rev[x]) {
swap(lson, rson);
if(lson) rev[lson] ^= ;
if(rson) rev[rson] ^= ;
rev[x] = ;
}
} int NewNode(int f, int k, int kind) {
int x = k;
fa[x] = f;
rev[x] = ch[x][] = ch[x][] = ;
sz[x] = ; ch[f][kind] = x;
return x;
} void Build(int l, int r, int &x, int f, int kind) {
if(l > r) return ;
int m = (l + r) >> ;
x = NewNode(f, m, kind);
Build(l, m - , ch[x][], x, );
Build(m + , r, ch[x][], x, );
PushUp(x);
} void Init() {
root = ;
ch[][] = ch[][] = fa[] = rev[] = sz[] = ;
root = NewNode(, n + , );
rootkey = NewNode(root, n + , );
sz[root] = ;
Build(, n, keytree, rootkey, );
PushUp(rootkey); PushUp(root);
} void Rotate(int x, int kind) {
int y = fa[x], z = fa[y];
PushDown(y); PushDown(x);
ch[y][!kind] = ch[x][kind];
if(ch[x][kind]) fa[ch[x][kind]] = y;
if(z) {
if(y == ch[z][]) ch[z][] = x;
else ch[z][] = x;
}
fa[x] = z; fa[y] = x;
ch[x][kind] = y;
PushUp(y);
} void Splay(int x, int goal) {
PushDown(x);
while(fa[x] != goal) {
int y = fa[x], z = fa[y];
PushDown(z); PushDown(y); PushDown(x);
int kind1 = x == ch[y][];
int kind2 = y == ch[z][];
if(z == goal) {
Rotate(x, kind1);
} else {
if(kind1 == kind2) Rotate(y, kind1);
else Rotate(x, kind1);
Rotate(x, kind2);
}
}
PushUp(x);
if(!goal) root = x;
} void RTO(int k, int goal) {
int x = root;
PushDown(x);
while(sz[lson] + != k) {
if(sz[lson] >= k) x = lson;
else k -= sz[lson] + , x = rson;
PushDown(x);
}
Splay(x, goal);
} void Travel(int x) {
if(lson) Travel(lson);
printf("travel : %d\n", x);
if(rson) Travel(rson);
PushUp(x);
} int Suf(int x) { // 找后继
if(rson) {
PushDown(x);
x = rson;
while(lson) {
x = lson;
PushDown(x);
}
}
return x;
} int Query(int l, int r) {
Splay(r, ); // 把原来节点的位置旋转到root位置
int ans = sz[ch[root][]]; // 因为多了一个节点,所以不用+1
RTO(l, ); // 把第l个数的前一个旋到root
Splay(Suf(r), root); // 把后继旋到ch[root][1]
rev[keytree] ^= ; //区间翻转
return ans;
} }spy; bool cmp(const node &a, const node &b) {
if(a.val == b.val) return a.id < b.id;
return a.val < b.val;
} int main() {
int n;
while(scanf("%d", &n), n) {
spy.n = n;
for(int i = ; i <= n; i++) {
scanf("%d", &spy.num[i]);
a[i].id = i;
a[i].val = spy.num[i];
}
sort(a + , a + + n, cmp);
spy.Init();
for(int i = ; i <= n; i++) {
int ans;
ans = spy.Query(i, a[i].id);
if(i == n) printf("%d\n", ans);
else printf("%d ", ans);
}
}
return ;
}