本文共 4108 字，大约阅读时间需要 13 分钟。
传送门：
由于询问只有1e5次，但n<=1e8，因此会有大量没用到的点，将这些点离散一下，单独提取出需要Top操作的点
（吐槽：用通常的splay做法超时了，又换了种写法结果就快了几倍。。。
#include #define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define first x#define second y#define eps 1e-8using namespace std;typedef long long LL;typedef pair PII;const int inf = 0x3f3f3f3f;const int MX = 2e5 + 5;struct Query { char op; int x, id;} que[MX];bool cmp1(Query q1, Query q2) { return q1.x < q2.x;}bool cmp2(Query q1, Query q2) { return q1.id < q2.id;}int T, n, m, nn;int root;int ch[MX][2], fa[MX];int s[MX], t[MX];int sz[MX], num[MX];void NewNode(int &rt, int father, int k) { rt = k; fa[rt] = father; ch[rt][0] = ch[rt][1] = 0; sz[rt] = num[rt] = t[rt] - s[rt] + 1;}void PushUP(int rt) { int ls = ch[rt][0], rs = ch[rt][1]; sz[rt] = sz[ls] + sz[rs] + num[rt];}void build(int &rt, int l, int r, int father) { if (l > r) return; int m = (l + r) >> 1; NewNode(rt, father, m); build(ch[rt][0], l, m - 1, rt); build(ch[rt][1], m + 1, r, rt); PushUP(rt);}void init_zero() { ch[0][0] = ch[0][1] = sz[0] = num[0] = fa[0] = 0;}void init() { root = nn = 0; init_zero(); int prex = 0; sort(que + 1, que + m + 1, cmp1); for (int i = 1; i <= m; i++) { if (que[i].op == 'T' && que[i].x != prex) { if (prex + 1 < que[i].x) { s[++nn] = prex + 1; t[nn] = que[i].x - 1; } s[++nn] = que[i].x; t[nn] = que[i].x; prex = que[i].x; } } if (prex < n) { s[++nn] = prex + 1; t[nn] = n; } build(root, 1, nn, 0); PushUP(root);}void Link(int x, int y, int c) { fa[x] = y; ch[y][c] = x;}void Rotate(int x, int c) { //c=0表示左旋,c=1表示右旋 int y = fa[x]; Link(x, fa[y], ch[fa[y]][1] == y); Link(ch[x][c], y, !c); Link(y, x, c); PushUP(y); //y变成x子节点,只要更新y}void Splay(int x, int f) { while (fa[x] != f) { int y = fa[x]; if (fa[y] == f) Rotate(x, ch[y][0] == x); else { int t = ch[fa[y]][0] == y; if (ch[y][t] == x) Rotate(x, !t); else Rotate(y, t); Rotate(x, t); } } PushUP(x); //更新x if (f == 0) root = x;}int Get_Min(int rt) { while (ch[rt][0]) rt = ch[rt][0]; return rt;}void Delete() { if (ch[root][0] == 0 || ch[root][1] == 0) { root = ch[root][0] + ch[root][1];//如果只有一个儿子则把儿子作为根节点 fa[root] = 0; return; } int rmin = Get_Min(ch[root][1]); Splay(rmin, root); ch[ch[root][1]][0] = ch[root][0];//左子树挂在右边最小的节点的左边 fa[ch[root][0]]=ch[root][1]; root = ch[root][1]; //把右边最小的节点作为根节点 fa[root] = 0; PushUP(root);}int B_search(int x) { //二分查找x属于哪一段 int le = 1, re = nn; while (le <= re) { int mid = (le + re) / 2; if (s[mid] <= x && x <= t[mid])return mid; if (x < s[mid])re = mid - 1; else le = mid + 1; } return -1;}//将点x放到最前面void Top(int x) { int rt = B_search(x); Splay(rt, 0); Delete(); //删掉第x个点 Splay(Get_Min(root), 0);//得到最左边的点 ch[rt][0] = 0; ch[rt][1] = root; //将第x个点放在第一个点前面 fa[root] = rt; root = rt; fa[root] = 0; PushUP(root);}int Query(int x) { int rt = B_search(x); Splay(rt, 0); return sz[ch[root][0]] + x - s[rt] + 1;}int Get_Rank(int rt, int k) { int t = sz[ch[rt][0]]; if (k <= t)return Get_Rank(ch[rt][0], k); else if (k <= t + num[rt]) return s[rt] + k - t - 1; else return Get_Rank(ch[rt][1], k - t - num[rt]);}int main() { //freopen("in.txt", "r", stdin); scanf("%d", &T); int cas = 0; while (T--) { printf("Case %d:\n", ++cas); scanf("%d%d", &n, &m); char op[10]; for (int i = 1, x; i <= m; i++) { scanf("%s%d", op, &x); que[i].op = op[0]; que[i].x = x; que[i].id = i; } init(); sort(que + 1, que + m + 1, cmp2); for (int i = 1; i <= m; i++) { if (que[i].op == 'T') Top(que[i].x); else if (que[i].op == 'R') printf("%d\n", Get_Rank(root, que[i].x)); else printf("%d\n", Query(que[i].x)); } } return 0;}
转载地址：http://npwpn.baihongyu.com/