Splay 学习笔记

Splay 模板（p3369 普通平衡树）

这是 Splay 的权值树，即按照权值排序。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 
 const int N = 1000000, INF = 0x3f3f3f3f;
 int n, opt, x, root = 0, cnt = 0, par[N], ch[N][2], val[N], rep[N], siz[N]; 
 
 struct Splay
 {
     void push_up(int x)
     {
         siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + rep[x];
     }
     int check(int x) { return ch[par[x]][1] == x ? 1 : 0; }
     void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x);
     }
     void splay(int x, int goal)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) root = x;
     }
     void find(int x)
     {
         int cur = root;
         while(ch[cur][x > val[cur]] && x != val[cur])
             cur = ch[cur][x > val[cur]];
         splay(cur, 0);
     }
     int kth(int k)
     {
         int cur = root;
         while(true)
         {
             if(ch[cur][0] && k <= siz[ch[cur][0]]) cur = ch[cur][0];
             else if(siz[ch[cur][0]] + rep[cur] < k)
                 k -= siz[ch[cur][0]] + rep[cur], cur = ch[cur][1];
             else { splay(cur, 0); return cur; }
         }
     }
     int precur(int x)
     {
         find(x);
         int cur = ch[root][0];
         if(val[root] < x) return root;
         while(ch[cur][1]) cur = ch[cur][1];
         splay(cur, 0);
         return cur;
     }
     int succes(int x)
     {
         find(x);
         int cur = ch[root][1];
         if(val[root] > x) return root;
         while(ch[cur][0]) cur = ch[cur][0];
         splay(cur, 0);
         return cur;
     } 
     void insert(int x)
     {
         int cur = root, p = 0;
         while(cur && val[cur] != x)
             p = cur, cur = ch[cur][x > val[cur]];
         if(cur) rep[cur]++;
         else
         {
             cur = ++cnt;
             if(p) ch[p][x > val[p]] = cur;
             ch[cur][0] = ch[cur][1] = 0, par[cur] = p;
             val[cur] = x, siz[cur] = rep[cur] = 1;
         }
         splay(cur, 0);
     }
     void remove(int x)
     {
         int last = precur(x), next = succes(x);
         splay(last, 0), splay(next, last);
         int del = ch[next][0];
         if(rep[del] > 1) rep[del]--, splay(del, 0);
         else ch[next][0] = 0;
         push_up(next), push_up(root);
     }
 } splay;
 
 int main()
 {
     scanf("%d", &n);
     splay.insert(INF), splay.insert(-INF);
     for(int i = 1; i <= n; i++)
     {
         scanf("%d%d", &opt, &x);
         if(opt == 1) splay.insert(x);
         if(opt == 2) splay.remove(x);
         if(opt == 3) splay.find(x), printf("%d\n", siz[ch[root][0]]);
         if(opt == 4) printf("%d\n", val[splay.kth(x + 1)]);
         if(opt == 5) printf("%d\n", val[splay.precur(x)]);
         if(opt == 6) printf("%d\n", val[splay.succes(x)]);
     }
     return 0;
 }

Splay 模板 2（p3391 文艺平衡树）

翻转 \([l,r]\) 时将 \(l-1\) \(rotate\) 到根，将 \(r+1\) \(rotate\) 到 \(l-1\) 的右儿子。很显然 \(>l-1\) 且 \(<r+1\) 的只有 \(l--r\)。所以 \([l,r]\) 区间都在 \(r+1\) 的左儿子上了。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int N = 1000000, INF = 0x3f3f3f3f;
 int n, m, x, y, cnt = 0, root = 1;
 int tag[N], num[N], par[N], siz[N], val[N], ch[N][2];
 struct Splay
 {
     int check(int x) { return ch[par[x]][1] == x; }
     void push_up(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; }
     int build(int l, int r, int p)
     {
         if(l > r) return 0;
         int now = ++cnt, mid = (l + r) / 2;
         if(l == r)
         siz[now] = 1;
         val[now] = num[mid], par[now] = p;
         ch[now][0] = ch[now][1] = 0;
         ch[now][0] = build(l, mid - 1, now);
         ch[now][1] = build(mid + 1, r, now);
         push_up(now);
         return now;
     }
     void push_down(int x)
     {
         if(x && !tag[x]) return ;
         tag[ch[x][0]] ^= 1, tag[ch[x][1]] ^= 1;
         swap(ch[x][0], ch[x][1]);
         tag[x] = 0;
     }
     void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x);
     }
     void splay(int x, int goal)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) root = x;
     }
     int kth(int k)
     {
         int cur = root;
         while(true)
         {
             push_down(cur);
             if(ch[cur][0] && 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 { splay(cur, 0); return cur; }
         }
     }
     void reverse(int l, int r)
     {
         l = kth(l), r = kth(r + 2);
         splay(l, 0), splay(r, l);
         tag[ch[ch[root][1]][0]] ^= 1;
     }
     void print(int x)
     {
         push_down(x);
         if(ch[x][0]) print(ch[x][0]);
         if(val[x] >= 1 && val[x] <= n) printf("%d ", val[x]);
         if(ch[x][1]) print(ch[x][1]);
     }
 } splay;
 
 int main()
 {
     scanf("%d%d", &n, &m);
     for(int i = 1; i <= n + 2; i++) num[i] = i - 1;
     splay.build(1, n + 2, 0);
     for(int i = 1; i <= m; i++)
     {
         scanf("%d%d", &x, &y);
         splay.reverse(x, y);
     }
     splay.print(root);
     return 0;
 } 

p2234 HNOI2002 营业额统计

要求在每个数插入之前查找它的前驱和后继，很容易想到用平衡树维护。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <cmath>
 #include <map>
 using namespace std;
 
 const int N = 1000000, INF = 0x3f3f3f3f;
 int n, a, now, last, next, ans = 0, root = 0, tot = 0;
 int par[N], ch[N][2], rep[N], val[N], siz[N];
 map <int, int> cnt;
 struct Splay
 {
     void push_up(int x)
     {
         siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + rep[x];
     }
     int check(int x) { return ch[par[x]][1] == x; }
     void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x);
     }
     void splay(int x, int goal)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) root = x;
     }
     void insert(int x)
     {
         int cur = root, p = 0;
         while(cur && val[cur] != x)
             p = cur, cur = ch[cur][x > val[cur]];
         if(cur) rep[cur]++;
         else
         {
             cur = ++tot;
             if(p) ch[p][x > val[p]] = cur;
             par[cur] = p, ch[cur][0] = ch[cur][1] = 0;
             siz[cur] = rep[cur] = 1, val[cur] = x;
         }
         splay(cur, 0);
     }
     void find(int x)
     {
         int cur = root;
         while(ch[cur][x > val[cur]] && val[cur] != x)
             cur = ch[cur][x > val[cur]];
         splay(cur, 0);
     }
     int precur(int x)
     {
         find(x);
         int cur = ch[root][0];
         if(val[root] < x) return root;
         while(ch[cur][1]) cur = ch[cur][1];
         splay(cur, 0);
         return cur;
     }
     int succes(int x)
     {
         find(x);
         int cur = ch[root][1];
         if(val[root] > x) return root;
         while(ch[cur][0]) cur = ch[cur][0];
         splay(cur, 0);
         return cur;
     }
 } splay;
 
 int main()
 {
     scanf("%d%d", &n, &a);
     splay.insert(INF), splay.insert(-INF);
     splay.insert(a), ans = a, cnt[a]++;
     for(int i = 2; i <= n; i++)
     {
         scanf("%d", &a);
         if(cnt[a] == 0)
         {
             now = INF;
             last = splay.precur(a), next = splay.succes(a);
             if(val[last] != -INF) now = a - val[last];
             if(val[next] != INF) now = min(now, val[next] - a);
             if(now != INF) ans += now;
         }
         splay.insert(a), cnt[a]++;
     }
     printf("%d", ans);
     return 0;
 } 

SP1716 GSS3 - Can you answer these queries III

这题跟 Splay 没有什么关系，但它是下一题的前置芝士。

因为要求支持带修的最大子段和，可以使用线段树维护。主要问题是如何使用两个儿子的值求出父亲的值（即 push_up 操作的实现）

设 \(prel\) 表示从区间最左端开始的最大子段和，\(prer\) 表示从区间最右端点开始的最大子段和，\(sum\) 表示区间和，\(res\) 表示区间的最大子段和。（用 \(l\) 表示左儿子，\(r\) 表示右儿子）

\(sum\) 的更新比较简单，可以直接更新。

\(prel\) 的更新有两种情况：仅存在于左子树中；跨过左子树进入右子树中。在两者之间取 \(max\)。\(prer\) 的更新同理。

\(prel[x] = max(prel[l], sum[l] + prel[r])\)

\(res\) 的更新有三种情况：左子树的 \(res\)，右子树的 \(res\)，左子树的 \(prer\) + 右子树的 \(prel\)。在三者之间取 \(max\)。

\(res[x] = max(max(res[l], res[r]), prer[l] + prel[r])\)

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 using namespace std;
 
 const int N = 1000000;
 int n, q, opt, x, y, a[N];
 struct node
 {
     int sum, prel, prer, res;
 } st[N];
 struct Segment_Tree
 {
     void push_up(int x)
     {
         st[x].sum = st[x * 2].sum + st[x * 2 + 1].sum;
         st[x].prel = max(st[x * 2].prel, st[x * 2].sum + st[x * 2 + 1].prel);
         st[x].prer = max(st[x * 2 + 1].prer, st[x * 2 + 1].sum + st[x * 2].prer);
         st[x].res = max(st[x * 2].res, st[x * 2 + 1].res);
         st[x].res = max(st[x].res, st[x * 2].prer + st[x * 2 + 1].prel);
     }
     void build(int x, int l, int r)
     {
         if(l == r)
         {
             st[x].sum = a[l];
             st[x].prel = st[x].prer = st[x].res = a[l];
             return ;
         }
         int mid = (l + r) / 2;
         build(x * 2, l, mid);
         build(x * 2 + 1, mid + 1, r);
         push_up(x);
     }
     void update(int x, int l, int r, int std, int k)
     {
         if(l > std || r < std) return ;
         if(std == l && std == r)
         {
             st[x].sum = k;
             st[x].prel = st[x].prer = st[x].res = k;
             return ;
         }
         int mid = (l + r) / 2;
         update(x * 2, l, mid, std, k);
         update(x * 2 + 1, mid + 1, r, std, k);
         push_up(x);
     }
     node query(int x, int l, int r, int stdl, int stdr)
     {
         if(stdl <= l && stdr >= r) return st[x];
         int mid = (l + r) / 2;
         if(stdr <= mid) return query(x * 2, l, mid, stdl, stdr);
         if(stdl > mid) return query(x * 2 + 1, mid + 1, r, stdl, stdr);
         node A = query(x * 2, l, mid, stdl, stdr), res;
         node B = query(x * 2 + 1, mid + 1, r, stdl, stdr);
         res.prel = max(A.prel, A.sum + B.prel);
         res.prer = max(B.prer, B.sum + A.prer);
         res.res = max(A.prer + B.prel, max(A.res, B.res));
         return res;
     }
 } tree;
 
 int main()
 {
     scanf("%d", &n);
     for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
     tree.build(1, 1, n);
     scanf("%d", &q);
     for(int i = 1; i <= q; i++)
     {
         scanf("%d%d%d", &opt, &x, &y);
         if(opt == 0) tree.update(1, 1, n, x, y);
         else printf("%d\n", tree.query(1, 1, n, x, y).res);
     }
     return 0;
 }

p2042 NOI2005 维护数列

恶心题，不过可以提高码力。对于 Insert 操作，先对所有需要 Insert 的数建立一棵平衡树，插入到 \(>posi\) 且 \(<posi+1\) 的位置。

另外，本题的最大子段和与上一题大致相同，在旋转的时候，\(prel[x]\) 和 \(prer[x]\) 需要互换。另外需要注意一些细节，例如最大子段和至少要选择一个数字。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <queue>
 using namespace std;
 
 const int N = 10000000, INF = 0x3f3f3f3f;
 struct node { int prel, prer, sum, res; } st[N];
 int n, m, a, posi, tot, c, root = 1, cnt = 0;
 int par[N], val[N], num[N], ch[N][2], siz[N], flt[N], rev[N];
 string opt; 
 queue <int> q;
 struct Splay
 {
     int check(int x) { return ch[par[x]][1] == x; }
     void push_up(int x)
     {
         int l = ch[x][0], r = ch[x][1];
         siz[x] = siz[l] + siz[r] + 1;
         st[x].sum = st[l].sum + st[r].sum + val[x];
         if(!l) st[l].res = -INF;
         if(!r) st[r].res = -INF;
         st[x].prel = max(st[l].prel, st[l].sum + st[r].prel + val[x]);
         st[x].prer = max(st[r].prer, st[r].sum + st[l].prer + val[x]);
         st[x].res = max(max(st[l].res, st[r].res), st[l].prer + st[r].prel + val[x]);
     }
     void push_down(int x)
     {
         int l = ch[x][0], r = ch[x][1];
         if(flt[x])
         {
             if(l)
             {
                 val[l] = val[x], flt[l] = 1, st[l].sum = val[x] * siz[l];
                 if(val[x] >= 0)
                     st[l].res = st[l].prel = st[l].prer = st[l].sum;
                 else st[l].res = val[x], st[l].prel = st[l].prer = 0;
             }
             if(r)
             {
                 val[r] = val[x], flt[r] = 1, st[r].sum = val[x] * siz[r];
                 if(val[x] >= 0)
                     st[r].res = st[r].prel = st[r].prer = st[r].sum;
                 else st[r].res = val[x], st[r].prel = st[r].prer = 0;
             }
             flt[x] = rev[x] = 0;
         }
         if(rev[x])
         {
             if(l) rev[l] ^= 1;
             if(r) rev[r] ^= 1;
             swap(ch[x][0], ch[x][1]);
             if(l) swap(st[l].prel, st[l].prer);
             if(r) swap(st[r].prel, st[r].prer);
             rev[x] = 0;
         }
         push_up(x);
     }
     int newID()
     {
         if(!q.empty())
         {
             int res = q.front();
             q.pop(); return res;
         }
         else return ++cnt;
     }
     int build(int l, int r, int p)
     {
         if(l > r) return 0;
         int now = newID(), mid = (l + r) / 2;
         rev[now] = flt[now] = 0;
         val[now] = st[now].sum = num[mid];
         siz[now] = 1, par[now] = p;
         st[now].prel = st[now].prer = st[now].res = num[mid];
         ch[now][0] = build(l, mid - 1, now);
         ch[now][1] = build(mid + 1, r, now);
         push_up(now);
         return now;
     }
     void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x);
     }
     void splay(int x, int goal)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) root = x;
     }
     int kth(int k)
     {
         int cur = root;
         while(true)
         {
             push_down(cur);
             if(ch[cur][0] && siz[ch[cur][0]] >= k) cur = ch[cur][0];
             else if(siz[ch[cur][0]] + 1 < k)
                 k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
             else { splay(cur, 0); return cur; }
         }
     }
     void rubish(int x)
     {
         q.push(x);
         if(ch[x][0]) rubish(ch[x][0]);
         if(ch[x][1]) rubish(ch[x][1]);
     }
     void insert(int start, int rt)
     {
         int l = kth(start + 1), r = kth(start + 2);
         splay(l, 0), splay(r, l);
         ch[ch[root][1]][0] = rt;
         par[rt] = ch[root][1];
         push_up(ch[root][1]), push_up(root);
     }
     void remove(int l, int r)
     {
         l = kth(l), r = kth(r + 2);
         splay(l, 0), splay(r, l);
         rubish(ch[ch[root][1]][0]);
         ch[ch[root][1]][0] = 0;
         push_up(ch[root][1]), push_up(root);
     }
     void flat(int l, int r, int k)
     {
         l = kth(l), r = kth(r + 2), splay(l, 0), splay(r, l);
         int x = ch[ch[root][1]][0];
         flt[x] = 1, val[x] = k, st[x].sum = k * siz[x];
         if(k >= 0) st[x].prel = st[x].prer = st[x].res = st[x].sum;
         else st[x].prel = st[x].prer = 0, st[x].res = k;
         push_up(ch[root][1]), push_up(root);
     }
     void reverse(int l, int r)
     {
         l = kth(l), r = kth(r + 2), splay(l, 0), splay(r, l);
         int x = ch[ch[root][1]][0];
         rev[x] ^= 1, swap(st[x].prel, st[x].prer);
         push_down(x);
         push_up(ch[root][1]), push_up(root);
     }
     int getsum(int l, int r)
     {
         l = kth(l), r = kth(r + 2);
         splay(l, 0), splay(r, l);
         push_up(ch[root][1]), push_up(root);
         return st[ch[ch[root][1]][0]].sum;
     }
 } splay;
 
 int main()
 {
     scanf("%d%d", &n, &m);
     num[1] = num[n + 2] = -INF;
     for(int i = 2; i <= n + 1; i++) scanf("%d", &num[i]);
     root = splay.build(1, n + 2, 0);
     for(int i = 1; i <= m; i++)
     {
         cin >> opt;
         if(opt[0] == 'I')
         {
             scanf("%d%d", &posi, &tot);
             for(int j = 1; j <= tot; j++) scanf("%d", &num[j]);
             splay.insert(posi, splay.build(1, tot, splay.newID()));
         }
         if(opt[0] == 'D')
         {
             scanf("%d%d", &posi, &tot);
             splay.remove(posi, posi + tot - 1);
         }
         if(opt[0] == 'M' && opt[opt.size() - 1] == 'E')
         {
             scanf("%d%d%d", &posi, &tot, &c);
             splay.flat(posi, posi + tot - 1, c);
         }
         if(opt[0] == 'R')
         {
             scanf("%d%d", &posi, &tot);
             splay.reverse(posi, posi + tot - 1);
         }
         if(opt[0] == 'G')
         {
             scanf("%d%d", &posi, &tot);
             printf("%d\n", splay.getsum(posi, posi + tot - 1));
         }
         if(opt[0] == 'M' && opt[opt.size() - 1] == 'M')
             printf("%d\n", st[root].res);
     }
     return 0;
 }

p3224 HNOI2012 永无乡

初始对每一个连通块都建立一棵平衡树。每次加进一座桥，就把相应的两棵平衡树合并。使用启发式合并，每次把节点数小的树合并到节点数大的树上。

因为并不会卡常，吸氧才通过最后一个点。

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 
 const int N = 1000000;
 int n, m, cnt = 0, root = 0, a, b, q;
 int fa[N], val[N], siz[N], num[N], rem[N], ch[N][2], par[N], rot[N];
 char opt;
 
 inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
 
 struct Splay
 {
     inline int check(int x) { return ch[par[x]][1] == x; }
     inline void push_up(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; }
     inline void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x);
     }
     inline void splay(int x, int goal, int fd)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) rot[fd] = x;
     }
     inline void insert(int x, int fd)
     {
         int cur = rot[fd], p = 0;
         while(cur) p = cur, cur = ch[cur][val[x] > val[cur]];
         par[x] = p, ch[p][val[x] > val[p]] = x;
         splay(x, 0, fd);
     }
     void remem(int x)
     {
         rem[++cnt] = x;
         if(ch[x][0]) remem(ch[x][0]);
         if(ch[x][1]) remem(ch[x][1]);
         ch[x][0] = ch[x][1] = 0, siz[x] = 1;
     }
     inline void add(int x, int fdy)
     {
         remem(x);
         for(int i = 1; i <= cnt; i++) insert(rem[i], fdy);
     }
     inline int kth(int k, int fd)
     {
         int cur = rot[fd];
         while(true)
         {
             if(ch[cur][0] && siz[ch[cur][0]] >= k) cur = ch[cur][0];
             else if(siz[ch[cur][0]] + 1 < k)
                 k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
             else { splay(cur, 0, fd); return cur; }
         }
     }
 } splay; 
 
 inline int read()
 {
     char c = getchar(); int x = 0, f = 1;
     while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
     while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); } 
     return f * x;
 }
 
 int main()
 {
     n = read(), m = read();
     for(int i = 1; i <= n; i++) val[i] = read();
     for(int i = 1; i <= n; i++) fa[i] = rot[i] = i, siz[i] = 1;
     for(int i = 1; i <= m; i++)
     {
         a = read(), b = read();
         splay.insert(rot[find(a)], find(b));
         fa[find(a)] = find(b);
     }
     q = read();
     for(int i = 1; i <= q; i++)
     {
         cin >> opt;
         if(opt == 'B')
         {
             a = read(), b = read();
             cnt = 0;
             if(find(a) == find(b)) continue;
             if(siz[rot[find(a)]] > siz[rot[find(b)]]) swap(a, b);
             splay.add(rot[find(a)], find(b));
             fa[find(a)] = find(b);
         }
         if(opt == 'Q')
         {
             a = read(), b = read();
             if(siz[rot[find(a)]] < b) printf("-1\n");
             else printf("%d\n", splay.kth(b, find(a)));
         }
     }
     return 0;
 }

p1486 NOI2004 郁闷的出纳员

首先注意到加工资和扣工资的操作最多只有 \(100\) 个，可以直接暴力，并且把工资不足的人暴力删掉。

另外，不要在 \(dfs\) 整棵树的时候做任何操作，否则会因为改变父子关系导致 MLE

 #include <iostream>
 #include <cstdio>
 #include <cstring>
 using namespace std;
 
 const int N = 101000;
 int n, min_, k, leave = 0, root = 0, cnt = 0, tot;
 int ch[N][2], par[N], siz[N], rep[N], val[N], del[N];
 char opt;
 struct Splay
 {
     int check(int x) { return ch[par[x]][1] == x; }
     void push_up(int x)
     {
         siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + rep[x];
     }
     void rotate(int x)
     {
         int y = par[x], z = par[y], k = check(x), w = ch[x][k ^ 1];
         ch[y][k] = w, par[w] = y;
         ch[z][check(y)] = x, par[x] = z;
         ch[x][k ^ 1] = y, par[y] = x;
         push_up(y), push_up(x); 
     }
     void splay(int x, int goal)
     {
         while(par[x] != goal)
         {
             int y = par[x], z = par[y];
             if(z != goal)
             {
                 if(check(x) == check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
         }
         if(goal == 0) root = x;
     }
     void insert(int x)
     {
         int cur = root, p = 0;
         while(cur && val[cur] != x)
             p = cur, cur = ch[cur][x > val[cur]];
         if(cur) rep[cur]++;
         else
         {
             cur = ++cnt;
             if(p) ch[p][x > val[p]] = cur;
             par[cur] = p, ch[cur][0] = ch[cur][1] = 0;
             val[cur] = x, siz[cur] = rep[cur] = 1;
         }
         splay(cur, 0);
     }
     int kth(int k)
     {
         int cur = root;
         while(true)
         {
             if(ch[cur][0] && siz[ch[cur][0]] >= k) cur = ch[cur][0];
             else if(siz[ch[cur][0]] + rep[cur] < k)
                 k -= siz[ch[cur][0]] + rep[cur], cur = ch[cur][1];
             else { splay(cur, 0); return cur; }
         }
     }
     int precur(int x)
     {
         splay(x, 0);
         int cur = ch[root][0];
         while(ch[cur][1]) cur = ch[cur][1];
         return cur;
     }
     int succes(int x)
     {
         splay(x, 0);
         int cur = ch[root][1];
         while(ch[cur][0]) cur = ch[cur][0];
         return cur;
     }
     void remove(int x)
     {
         int last = precur(x), next = succes(x);
         splay(last, 0), splay(next, last);
         leave += rep[ch[next][0]], ch[next][0] = 0;
         push_up(next), push_up(last);
     }
     void dfs(int x, int k)
     {
         if(x > 2) val[x] += k;
         if(val[x] < min_ && x > 2) del[++tot] = x;
         if(ch[x][0]) dfs(ch[x][0], k);
         if(ch[x][1]) dfs(ch[x][1], k);
     }
     void work(int k)
     {
         tot = 0; dfs(root, k);
         for(int i = 1; i <= tot; i++) remove(del[i]);
     }
 } splay;
 
 int main()
 {
     scanf("%d%d", &n, &min_);
     splay.insert(0x3f3f3f3f), splay.insert(-0x3f3f3f3f);
     for(int i = 1; i <= n; i++)
     {
         cin >> opt >> k;
         tot = 0;
         if(opt == 'I' && k >= min_) splay.insert(k);
         if(opt == 'A') splay.work(k);
         if(opt == 'S') splay.work(-k);
         if(opt == 'F')
         {
             int b = siz[root] - k;
             if(k > siz[root] - 2) printf("-1\n");
             else printf("%d\n", val[splay.kth(b)]);
         }
     }
     printf("%d", leave);
     return 0;
 }

Splay 学习笔记

原文：https://www.cnblogs.com/Andy-park/p/12388293.html