继续刷splay。orz
第一次遇到splay的离散化，留个纪念。传送门：Queue-jumpers
题目大意：
有 108 的人，一开始按照1,2,3…n排序，有q次操作。
一开始的编号为1,2,3…n，操作后编号不变。操作Top x，将编号为x的人放到最前面。
操作Rank x，告诉他编号为x的人排在哪里
操作Query x，告诉他第x位的人的编号是多少。
思路：
其实去掉 108 ，人数少一点，就是一个基本的splay裸题。
但是现在有 108 的人数，但是询问次数只有 105 。
这让我们很容易可以想到，把询问离线之后离散化。
但是只离散化询问的点是相对麻烦的。
因为你做了Top操作之后，他的子树的size一定为1。
但是我们在做new node的时候，对于最初的插入，size是需要通过计算离散化区间大小来得到的。
这样我么那就会写出两种new node 不是很好维护其实我们不妨在离散化点的时候，将他前一个点和后一个点，也顺带丢进去离散化里。
这些点是不会给操作到的，他们只是用来辅助算size的。
一个点的初始size为e[v] - s[v] + 1,这个e[v]和s[v]分别表示他的左端点和右端点。
那么他们要询问的点的size一开始一定是1，因为他的左端点和右端点都是自己。
而其我们做的就是辅助区间。二分的时候要自己手动实现一下
另外get_kth这个函数也需要改一改。其实操作麻烦的就只是Top而已。
我们可以先把他删除了，然后再将树上最小的点旋转到根，那么根的左子树一定是空的。然后对左子树进行插入就可以了
/* @resources: hdu 3436 @date: 2017-09-04 @author: QuanQqqqq @algorithm: splay */
#include <stdio.h>
#include <algorithm>
#include <string.h>#define ll long long
#define MAXN 100005using namespace std;int n;struct Question {char str[10];int x;
} qsn[MAXN];int pt[MAXN], ptlen; //离散化后的数组和长度
int s[MAXN], e[MAXN]; //这里储存离散化后的点，顺带把离散化后区间的点也储存，那些点只用来记size，不会被操作到
int cttn;int binary_search(int x) {int l = 0, r= cttn - 1, mid;while (l <= r) {mid = r + l >> 1;if (s[mid] <= x && e[mid] >= x) {return mid;}if (e[mid] < x) {l = mid + 1;} else {r = mid - 1;}}
}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]; //每个点的价值int node[MAX_SIZE]; //记录节点的位置int root, sz; //该树的根，该树的节点数int cnt; //中序遍历指针int num[MAX_SIZE];void Treaval(int x) {if (x) {Treaval(tree[x][0]);printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d\n", x, tree[x][0], tree[x][1], father[x], size[x]);Treaval(tree[x][1]);}}void debug() {printf("%d\n",root);Treaval(root);}//更新节点void push_up(int r) {size[r] = size[tree[r][0]] + size[tree[r][1]] + num[r];}void new_node(int &r, int fa, int v) {r = ++sz;father[r] = fa;val[r] = v;node[v] = r;size[r] = num[r] = e[v] - s[v] + 1;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;val[0] = num[root] = size[root] = tree[0][0] = tree[0][1] = father[0] = 0;build(root, 0, cttn - 1, root); //建一棵在n+1左边的完全二叉平衡树}void rotate(int x, int k) { //x是节点，k判断是左旋还是右旋int y = father[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;}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_min(int r) {push_up(r);while (tree[r][0]) {r = tree[r][0];push_up(r);}return r;}int get_next(int x) { //获得比x下标大一点的下标int rg = tree[x][1];if (rg == 0) { //这里可能出现，他爸爸也是没东西或者，他爸爸是他前一个的情况，那你就要反思一下你的splay是不是建错了return father[x];}while (tree[rg][0]) {rg = tree[rg][0];}return rg;}int get_pre(int x) { //获得比x下标小一点的下标int lf = tree[x][0];//这里可能出现lf为0while (tree[lf][0]) {lf = tree[lf][0];}return lf;}int get_kth(int r, int k) { //获得第k大的rootint siz = size[tree[r][0]];if (k <= siz) {return get_kth(tree[r][0], k);} else if (k <= siz + num[r]) { //这里要写小于等于号，因为里面有存在区间 return s[val[r]] + (k - siz) - 1;} else {return get_kth(tree[r][1], k - siz - num[r]);}}void del() { //这里删除被旋转到root的那个 if (!tree[root][0] || !tree[root][1]) {root = tree[root][0] + tree[root][1];father[root] = 0;return ;}int k = get_min(tree[root][1]); //找到最小的那个splay(k, root);tree[tree[root][1]][0] = tree[root][0];root = tree[root][1];father[tree[root][0]] = root;father[root] = 0;push_up(root);}void insert(int &r, int k, int fa) { //这里插入到最前的那个位置 if (r == 0) {new_node(r, fa, k);return ;}insert(tree[r][0], k, r);push_up(r);}void top_point(int a) {int y = node[a];splay(y, 0);del();insert(root, a, 0);splay(sz, 0); //听说这步不加会TLE}int get_rank(int x) {x = node[x];splay(x, 0);return size[tree[root][0]] + 1;}
};SplayTree spl;int q;void solve() {for (int i = 0; i < q; i++) {int idx = binary_search(qsn[i].x);if (qsn[i].str[0] == 'T') {spl.top_point(idx);} else if (qsn[i].str[0] == 'R') {printf("%d\n", spl.get_kth(spl.root, qsn[i].x));} else {printf("%d\n", spl.get_rank(idx));}}
}int main() {int T, cas = 1;scanf("%d", &T);while (T--) {scanf("%d %d", &n, &q);int len = 0;pt[len++] = 0;for (int i = 0; i < q; i++) {getchar();scanf("%s %d", qsn[i].str, &qsn[i].x);if (qsn[i].str[0] == 'Q' || qsn[i].str[0] == 'T') {pt[len++] = qsn[i].x;}}pt[len++] = n;cttn = 0;sort(pt, pt + len);for (int i = 1; i < len; i++) { //离散化if (pt[i] != pt[i - 1]) {if (pt[i] - pt[i - 1] > 1) {s[cttn] = pt[i - 1] + 1;e[cttn] = pt[i] - 1;cttn++;}s[cttn] = pt[i];e[cttn] = pt[i];cttn++;}}spl.clear();printf("Case %d:\n", cas++);solve();}
}