[题解]LuoGu2596：[ZJOI2006]书架

原题传送门 按顺序排列的数，每个数有权值 先确定好：权值只在输出用，在Splay中没用，按顺序建立Splay 分别确定每个操作的做法：

$Top$ $S$：将自己旋到根，把左儿子并成后继的左儿子，这样自己就成了top了，注意没有儿子的情况$Bottom$ $S$：将自己旋到根，把右儿子并成前驱的右儿子，这样自己就成了Bottom了，注意没有儿子的情况$Insert$ $S$ $T$：把自己旋到根，然后分情况讨论，首先，t=0等于没变；t=1的话，$swap(自己，后继)$；$t=-1，swap(自己，前驱)$$Ask$ $S$：把自己旋到根，$size[左儿子]$即为答案$Query$ $S$：$kth(S)即可$

然后是不是就可以秒掉了呀 Code：

#include <bits/stdc++.h> #define maxn 100010 using namespace std; int n, m, rt, sz, f[maxn], size[maxn], key[maxn], pos[maxn], son[maxn][2]; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } int get(int x){ return son[f[x]][1] == x; } void update(int x){ if (x){ size[x] = 1; if (son[x][0]) size[x] += size[son[x][0]]; if (son[x][1]) size[x] += size[son[x][1]]; } } void connect(int x, int y, int z){ if (x) f[x] = y; if (y) son[y][z] = x; } void rotate(int x){ int fa = f[x], ffa = f[fa], m = get(x), n = get(fa); connect(son[x][m ^ 1], fa, m); connect(fa, x, m ^ 1); connect(x, ffa, n); update(fa); update(x); } void splay(int x, int goal){ while (f[x] != goal){ int fa = f[x]; if (f[fa] != goal) rotate(get(x) == get(fa) ? fa : x); rotate(x); } if (!goal) rt = x; } void insert(int x){ int now = rt; while (son[now][1]) now = son[now][1]; key[++sz] = x, f[sz] = now, size[sz] = 1; son[sz][0] = son[sz][1] = 0, pos[x] = sz; if (now) son[now][1] = sz; update(now); splay(sz, 0); } void Top(int x){ splay(pos[x], 0); if (!son[rt][0]) return; if (!son[rt][1]){ son[rt][1] = son[rt][0], son[rt][0] = 0; return; } x = son[rt][1]; while (son[x][0]) x = son[x][0]; connect(son[rt][0], x, 0); son[rt][0] = 0; splay(son[x][0], 0); } void Bottom(int x){ splay(pos[x], 0); if (!son[rt][1]) return; if (!son[rt][0]){ son[rt][0] = son[rt][1], son[rt][1] = 0; return; } x = son[rt][0]; while (son[x][1]) x = son[x][1]; connect(son[rt][1], x, 1); son[rt][1] = 0; splay(son[x][1], 0); } void Ins(int x, int y){ splay(pos[x], 0); if (!y) return; if (y == 1){ int X = pos[x], Y = son[rt][1]; while (son[Y][0]) Y = son[Y][0]; swap(pos[x], pos[key[Y]]); swap(key[X], key[Y]); } else{ int X = pos[x], Y = son[rt][0]; while (son[Y][1]) Y = son[Y][1]; swap(pos[x], pos[key[Y]]); swap(key[X], key[Y]); } } int kth(int x){ int now = rt; while (1){ if (size[son[now][0]] >= x) now = son[now][0]; else if (size[son[now][0]] + 1 >= x) return key[now]; else x -= size[son[now][0]] + 1, now = son[now][1]; } } int main(){ n = read(), m = read(); for (int i = 1; i <= n; ++i){ int x = read(); insert(x); } while (m--){ char c = getchar(); for (; c != 'Q' && c != 'T' && c != 'B' && c != 'A' && c != 'I'; c = getchar()); int x = read(); if (c == 'T') Top(x); else if (c == 'B') Bottom(x); else if (c == 'I'){ int y = read(); Ins(x, y); } else if (c == 'A'){ splay(pos[x], 0); printf("%d\n", size[son[rt][0]]); } else printf("%d\n", kth(x)); } return 0; }