Problem
每次找到最小值，然后把它和它前面的数翻转，然后找第二小数······
然后输出这些数的下标。Solution
用splay维护，每次找到最小值，然后翻转前面区间。
Notice
细节操作巨烦无比。
Code
#include#include #include #include #include using namespace std;#define sqz main#define ll long long#define reg register int#define rep(i, a, b) for (reg i = a; i <= b; i++)#define per(i, a, b) for (reg i = a; i >= b; i--)#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)const int INF = 1e9, N = 100000;const double eps = 1e-6, phi = acos(-1.0);ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}int point = 0, root, pre, suf, ans, x[N + 5];struct Node{ int val, id;}T[N + 5];struct node{ int val[N + 5], son[2][N + 5], parent[N + 5], Min[N + 5], Size[N + 5], rev[N + 5]; inline void up(int u) { Size[u] = Size[son[0][u]] + Size[son[1][u]] + 1; Min[u] = val[u]; if (son[0][u]) Min[u] = min(Min[u], Min[son[0][u]]); if (son[1][u]) Min[u] = min(Min[u], Min[son[1][u]]); } inline void down(int u) { if (rev[u]) { swap(son[0][u], son[1][u]); rev[son[0][u]] ^= 1, rev[son[1][u]] ^= 1; rev[u] = 0; } } void Newnode(int &u, int from, int v) { u = ++point; son[0][u] = son[1][u] = 0; Min[u] = val[u] = v; Size[u] = 1, rev[u] = 0; parent[u] = from; } void Build(int &u, int l, int r, int from) { int mid = (l + r) >> 1; Newnode(u, from, x[mid]); if (l < mid) Build(son[0][u], l, mid - 1, u); if (r > mid) Build(son[1][u], mid + 1, r, u); up(u); } void Init(int n) { root = point = 0; son[0][0] = son[1][0] = parent[0] = Size[0] = rev[0] = 0; Min[0] = val[0] = N; Newnode(root, 0, N); Newnode(son[1][root], root, N); Build(son[0][son[1][root]], 1, n, son[1][root]); up(son[1][root]); up(root); } void Rotate(int x, int &rt) { int y = parent[x], z = parent[y]; int l = (son[1][y] == x), r = 1 - l; if (y == rt) rt = x; else if (son[0][z] == y) son[0][z] = x; else son[1][z] = x; parent[x] = z; parent[son[r][x]] = y, son[l][y] = son[r][x]; parent[y] = x, son[r][x] = y; up(y), up(x); } void Splay(int x, int &rt) { while (x != rt) { int y = parent[x], z = parent[y]; down(z), down(y), down(x); if (y != rt) { if ((son[0][z] == y) ^ (son[0][y] == x)) Rotate(x, rt); else Rotate(y, rt); } Rotate(x, rt); } } void Delete(int x) { Splay(x, root); if (son[0][x] * son[1][x] == 0) root = son[0][x] + son[1][x]; else { down(x); int t = son[1][x]; down(t); while (son[0][t] != 0) t = son[0][t], down(t); Splay(t, root); son[0][t] = son[0][x], parent[son[0][x]] = t; up(t); } parent[root] = 0; } int Find(int u, int num) { if (num == Size[son[0][u]] + 1) return u; else if (num <= Size[son[0][u]]) return Find(son[0][u], num); else return Find(son[1][u], num - Size[son[0][u]] - 1); } int Find_Min(int u, int tt) { down(u); if (val[u] == tt) return Size[son[0][u]] + 1; else if (Min[son[0][u]] == tt) return Find_Min(son[0][u], tt); else return Size[son[0][u]] + 1 + Find_Min(son[1][u], tt); }}Splay_tree;int cmp(Node X, Node Y){ return X.val < Y.val ||(X.val == Y.val && X.id < Y.id);}int sqz(){ int n; while (scanf("%d", &n) && n) { rep(i, 1, n) T[i].val = read(), T[i].id = i; sort(T + 1, T + n + 1, cmp); rep(i, 1, n) x[T[i].id] = i; Splay_tree.Init(n); rep(i, 1, n - 1) { int t = Splay_tree.Find_Min(root, i); printf("%d ", t + i - 2); Splay_tree.Splay(Splay_tree.Find(root, 1), root); Splay_tree.Splay(Splay_tree.Find(root, t), Splay_tree.son[1][root]); Splay_tree.rev[Splay_tree.son[0][Splay_tree.son[1][root]]] ^= 1; Splay_tree.Delete(Splay_tree.Find(root, t)); } printf("%d\n", n); }}