传送门：点击打开链接
题意：一种排序，找到最小的，然后讲整段翻转，把数字提前。
思路：看到旋转就应该想到用splay。问题是怎么知道第几大的数字当前是第几个。
这里有种方法，就是记录每个数字的节点编号，然后只要把这个节点Splay到根节点，那么size[son[root][0]]就是数字所在的位置了。
有个需要注意的地方，就是翻转的时候，一定要这样写，不然会出各种问题，上一道Splay题都没注意到这些细节侥幸过了，诶。。
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;const int MX = 1e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;int size[MX], num[MX], col[MX], n;
int son[MX][2], fa[MX], root, sz;
struct Data{int num,pos,id;bool operator<(const Data &P) const{if(num == P.num) return pos < P.pos;return num < P.num;}
}A[MX];
void Link(int x, int y, int c) {fa[x] = y; son[y][c] = x;
}
void push_up(int rt) {size[rt] = size[son[rt][0]] + size[son[rt][1]] + 1;
}
void Reverse(int rt){col[rt] ^= 1;swap(son[rt][0], son[rt][1]);
}
void push_down(int rt) {if(col[rt]) {Reverse(son[rt][0]);Reverse(son[rt][1]);col[rt] = 0;}
}
void Rotate(int x, int c) {int y = fa[x];push_down(y); push_down(x);Link(x, fa[y], son[fa[y]][1] == y);Link(son[x][!c], y, c);Link(y, x, !c);push_up(y);
}
void Splay(int x, int g) {push_down(x);while(fa[x] != g) {int y = fa[x], cx = son[y][1] == x, cy = son[fa[y]][1] == y;if(fa[y] == g) Rotate(x, cx);else {if(cx == cy) Rotate(y, cy);else Rotate(x, cx);Rotate(x, cy);}}push_up(x);if(!g) root = x;
}
void NewNode(int f, int &rt) {rt = ++sz;fa[rt] = f, size[rt] = 1;son[rt][0] = son[rt][1] = col[rt] = 0;
}
int Select(int k, int g) {int rt = root;while(size[son[rt][0]] != k) {if(size[son[rt][0]] > k) rt = son[rt][0];else k -= size[son[rt][0]] + 1, rt = son[rt][1];push_down(rt);}Splay(rt, g);return rt;
}
void Build(int l, int r, int &rt, int f) {if(l > r) return;int m = (l + r) >> 1, t;NewNode(f, rt);Build(l, m - 1, son[rt][0], rt);scanf("%d", &num[rt]); A[m].pos = m;A[m].num = num[rt]; A[m].id = rt;Build(m + 1, r, son[rt][1], rt);push_up(rt);
}
void Prepare(int n) {sz = 0;NewNode(0, root); num[1] = 0;NewNode(root, son[root][1]); num[2] = 0;Build(1, n, son[2][0], 2);sort(A + 1, A + n + 1);Splay(3, 0);
}
void Flip(int l, int r) {Select(l - 1, 0);Select(r + 1, root);Reverse(son[son[root][1]][0]);
}
int main() {//FIN;while(~scanf("%d", &n), n) {Prepare(n);for(int i = 1; i <= n; i++) {Splay(A[i].id, 0);int p = size[son[root][0]];Flip(i, p);printf("%d%c", p, i == n ? '\n' : ' ');}}return 0;
}