又抓了一道经典例题的splay。
这个主要是区间翻转，其中有一点树型dp的感觉。
传送门：Robotic Sort
题目大意：
每次拿第i位数和第i大的数之间的数进行翻转，这样每次翻转完毕之后第i位数一定是有序的。
每次输出第i大的数的位置，打印完毕后再进行翻转。
思路：
拿一棵splay数。按顺序插入数。
对于每个位置。维护他的序列号和值。
还要维护一个子树的最小值的位置。这个在每次操作的时候push_up一下就好了。
然后每次将第i - 1位旋转到root
将第i大的位的下一位旋转到root的右儿子结点
那么root的右儿子结点的左儿子树就是我们要进行翻转的区间。且这个子树的大小+i - 1就是我们要的答案。splay最重要的是。创点的时候，别忘了创一个最小点和一个最大点。因为这样做才能使最坏需要操作整个区间的时候，这个区间能在root的右儿子的左子树下。
/* @resources: @date: 2017-09-02 @author: QuanQqqqq @algorithm: splay */
#include <stdio.h>
#include <algorithm>
#include <string.h>#define ll long longusing namespace std;int n;int num[350010][2];struct SplayTree {const static int MAX_SIZE = 3e5 + 10;const static int INF = 0x7ffffff;int tree[MAX_SIZE][2], father[MAX_SIZE]; //该点的左右儿子，该点的爸爸节点，int size[MAX_SIZE]; //该点的子节点数int val[MAX_SIZE][2]; //每个点的价值int root, sz; //该树的根，该树的节点数int cnt; //中序遍历指针int rev[MAX_SIZE]; //翻转区间，懒惰更新int sum[MAX_SIZE]; //求子树的和int lazy[MAX_SIZE]; //求和，懒惰更新int mn[MAX_SIZE]; //记录最小值void Treaval(int x) {if (x) {Treaval(tree[x][0]);printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d %2d,sum = %2d\n", x, tree[x][0], tree[x][1], father[x], size[x], val[x][0], val[x][1], sum[x]);Treaval(tree[x][1]);}}void debug() {printf("%d\n",root);Treaval(root);}void modify(int x) {if (x) {rev[x] ^= 1;int tmp = tree[x][0];tree[x][0] = tree[x][1];tree[x][1] = tmp;}}bool is_small(int a, int b) {if (val[a][0] < val[b][0]) {return true;} else if (val[a][0] == val[b][0] && val[a][1] < val[b][1]) {return true;}return false;}//更新节点void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + 1;/*判断点*/mn[r] = r;if (tree[r][0] && is_small(mn[tree[r][0]], mn[r])) {mn[r] = mn[tree[r][0]];}if (tree[r][1] && is_small(mn[tree[r][1]], mn[r])) {mn[r] = mn[tree[r][1]];}}//lazy更新void push_down(int r) {if (rev[r]) { //翻转modify(tree[r][0]);modify(tree[r][1]);rev[r] = false;}}void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;val[r][0] = num[v][0];val[r][1] = num[v][1];size[r] = 1;mn[r] = r;rev[r] = tree[r][0] = tree[r][1] = 0;}void build(int &rt, int l, int r, int fa) { //建一棵满的二叉平衡树if (l > r) {return ;}int mid = l + r >> 1;new_node(rt, fa, mid);build(tree[rt][0], l, mid - 1, rt);build(tree[rt][1], mid + 1, r, rt);push_up(rt);}void clear() {sz = root = cnt = 0;num[0][0] = num[0][1] = size[root] = tree[0][0] = tree[0][1] = rev[0] = father[0] = sum[0] = lazy[0] = 0;memset(rev, 0, sizeof(rev));new_node(root, 0, 0);build(tree[root][1], 1, n + 1, root); //建一棵在n+1左边的完全二叉平衡树push_up(root);}void rotate(int x, int k) { //x是节点，k判断是左旋还是右旋int y = father[x];push_down(y);push_down(x);tree[y][!k] = tree[x][k]; //先变两边的儿子father[tree[x][k]] = y; //再将x的儿子的爸爸变成yif (father[y]) { //如果不是root，将y爸爸的儿子也变一下tree[father[y]][tree[father[y]][1] == y] = x;}father[x] = father[y]; //更新x的父亲成y的父亲father[y] = x; //更新y的父亲成xtree[x][k] = y; //更新x的儿子成ypush_up(y);}void splay(int x, int r) { //将x旋转到r的儿子，这里注意是儿子！if (r == 0) {root = x;}push_down(x);while (father[x] != r) {if (father[father[x]] == r) { //zig-steprotate(x, tree[father[x]][0] == x);return ;}int y = father[x];int k = tree[father[y]][0] == y; //判断上上层是否是左边if (tree[y][k] == x) { // zig-zag-steprotate(x, !k);rotate(x, k);} else { // zig-zig-steprotate(y, k);rotate(x, k);}}push_up(x);}int get_next(int x) { //获得比x下标大一点的值 push_down(x);int rg = tree[x][1];push_down(rg);if (rg == 0) {return father[x];}while (tree[rg][0]) {rg = tree[rg][0];push_down(rg);}return rg;}
};SplayTree spl;int main() {while (scanf("%d", &n) && n) {for (int i = 1; i <= n; i++) {scanf("%d", &num[i][0]);num[i][1] = i;}num[n + 1][0] = spl.INF;num[n + 1][1] = spl.INF;spl.clear();int mnode = 1, snode;for (int i = 0; i < n - 1; i++) {spl.splay(mnode, 0);mnode = spl.mn[spl.tree[spl.root][1]]; //找到右边最小值 spl.splay(mnode, spl.root); //这里splay操作一下保证有next，否则TLE snode = spl.get_next(mnode); //找到最小值的下一个位置 spl.splay(snode, spl.root); //旋转到根的右儿子结点 printf("%d ", i + spl.size[spl.tree[snode][0]]); //该点的左儿子节点即为区间里的数 spl.modify(spl.tree[snode][0]); //翻转一下 }printf("%d\n", n);}
}