BZOJ 1861
题意：给定一个排列，求对排列支持以下操作
Top S，将排列中的$S$放到排列最前面Bottom S，将排列中的$S$放到排列最后面Insert S T：若$S$的前面有$X$个数，则这个数放回去后它的前面有$X+T$个数 ($T∈(-1，0，1)$)Ask S：询问$S$前面有几个数Query S：询问从前往后第$S$个数是什么。
显然 Splay 可做，kth可以定每个数在排列中的位置
然后因为这里是排列，所以可以建立一个数组映射，即每个数在Splay上的点编号和数对应。
然后将Splay上的某点转到根之后的左子树大小即为该点在排列中的位置。
知识点：
1、函数功能写清楚
2、实在调不出来/想不出来可以放下来之后再看
3、Splay 的序列区间最好都建在 $[1,n+2]$，避免与$0$冲突，加上虚节点非常有用
4、Splay 维护序列一定要用build函数
5、对于维护序列的数据结构，可以通过某个操作来得到整个序列来查程序的错误
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<stack>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
int n, q, arr[MAXN], pos[MAXN];
int ch[MAXN][2], fa[MAXN], val[MAXN], siz[MAXN], sz, rt;
int rel(int x) {return ch[fa[x]][1] == x;}
void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;}
void rotate(int x) {
int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
ch[z][rel(y)] = x, fa[x] = z;
ch[y][k] = w, fa[w] = y;
ch[x][k ^ 1] = y, fa[y] = x;
pushup(y), pushup(x);
}
void splay(int x, int gl = 0) {
while (fa[x] != gl) {
int y = fa[x], z = fa[y];
if (z != gl) {
if (rel(x) == rel(y)) rotate(y); else rotate(x);
}
rotate(x);
}
if (!gl) rt = x;
}
int newNode(int v) {
val[++sz] = v, ch[sz][0] = ch[sz][1] = fa[sz] = 0, siz[sz] = 1;
pos[v] = sz;
return sz;
}
int build(int l, int r) {
if (l > r) return 0;
int mid = (l + r) >> 1;
int cur = newNode(arr[mid]);
if (l == r) return cur;
if ((ch[cur][0] = build(l, mid - 1))) fa[ch[cur][0]] = cur;
if ((ch[cur][1] = build(mid + 1, r))) fa[ch[cur][1]] = cur;
pushup(cur);
return cur;
}
int getnum(int x) { // 得到 x 点的位置
splay(x);
return siz[ch[x][0]];
}
int kth(int k) {
int cur = rt;
while (1) {
if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
else if (k > siz[ch[cur][0]] + 1) k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
else return cur;
}
}
void insert(int x, int p) { // 将 x 点插到 p 位置后面
int pre = kth(p + 1), succ = kth(p + 2);
splay(pre), splay(succ, pre);
ch[succ][0] = x, fa[x] = succ;
pushup(succ), pushup(pre);
splay(x);
}
void move(int x, int y) { // 将 x 位置上的移到 y 位置后面
int pre = kth(x), succ = kth(x + 2);
splay(pre), splay(succ, pre);
int fr = ch[succ][0];
ch[succ][0] = 0, fa[fr] = 0;
pushup(succ), pushup(pre);
insert(fr, y);
}
void clean() {
ms(arr, 0), ms(pos, 0), ms(ch, 0), ms(fa, 0), ms(val, 0), ms(siz, 0), sz = 0;
rt = 0;
}
int solve() {
scanf("%d%d", &n, &q);
clean();
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i + 1]);
rt = build(1, n + 2);
char s[10];
while (q--) {
int S, T;
scanf("%s", s);
if (s[0] == 'T')
scanf("%d", &S), move(getnum(pos[S]), 0);
if (s[0] == 'B')
scanf("%d", &S), move(getnum(pos[S]), n - 1);
if (s[0] == 'I')
scanf("%d%d", &S, &T), move(getnum(pos[S]), getnum(pos[S]) + T - 1);
if (s[0] == 'A')
scanf("%d", &S), printf("%d\n", getnum(pos[S]) - 1);
if (s[0] == 'Q')
scanf("%d", &S), printf("%d\n", val[kth(S + 1)]);
if (s[0] == 'G') { // tester
for (int i = 1; i <= n; ++i) printf("%d ", val[kth(i + 1)]);
printf("\n");
}
}
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
/*
10 1000
1 3 2 7 5 8 10 4 9 6
*/
