[CodeVS 1343] 蚱蜢：Splay Tree

本文主要是介绍[CodeVS 1343] 蚱蜢：Splay Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：N个数，J个操作（2 ≤ N ≤ 100 000, 1 ≤ J ≤ 100 000）。每个操作将第a个数往前或后移动b个，并询问跨越的这些数中的最大值，保证操作有效。

要求支持区间查询、增添删除，Splay是个不错的选择。

把第a个数删掉，再插到第b个数前面就好啦。有没有更有针对性的做法呢？

我是这样做的：假设把x移到y前面，x、y把一列数分为三段：a x b y c -> a b x y c

把x删除，插到y前面等价于把b和a合并。正好，为了查区间最大值，我们已经把b提取出来了。

#include <cstdio>
#include <algorithm>
const int MAX_N = 1e5, inf = 1<<30;
int N, a[MAX_N];struct Splay {static const int n = MAX_N+4, nil = n-1;int ptr, &root, ch[n][2], fa[n], sz[n], v[n], mx[n];int type(int x) { return x == ch[fa[x]][1]; }void up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; mx[x] = std::max(v[x], std::max(mx[ch[x][0]], mx[ch[x][1]])); }void set(int x, int d, int y) { fa[ch[x][d] = y] = x; }void rot(int x, int d){int y = ch[x][d];set(fa[x], type(x), y);set(x, d, ch[y][d^1]);set(y, d^1, x);up(x);up(y);}void splay(int x, int p=0){int y;while ((y = fa[x]) != p) {int z = fa[y], t1 = type(x);if (z != p) {int t2 = type(y);if (t1 == t2)rot(z, t2), rot(y, t1);elserot(y, t1), rot(z, t2);} elserot(y, t1);}}int new_node(int c){ch[ptr][0] = ch[ptr][1] = nil;sz[ptr] = 1;v[ptr] = mx[ptr] = c;return ptr++;}Splay(): ptr(1), root(ch[0][0]){sz[nil] = 0;v[nil] = mx[nil] = -inf;set(0, 0, new_node(0));set(1, 1, new_node(0));}void build(){build(0, N-1, 2, 0);up(2);up(1);}void build(int l, int r, int p, int t){if (l > r) return;int m = (l+r)/2, x = new_node(a[m]);set(p, t, x);build(l, m-1, x, 0);build(m+1, r, x, 1);up(x);}void join(int x, int y, int t){int p = x;while (ch[p][t] != nil)p = ch[p][t];splay(p, fa[x]);set(p, t, y);up(p);}int kth(int k, int p=0){int x = root;while (x != nil) {int s = sz[ch[x][0]];if (k == s+1) return splay(x, p), x;if (s >= k) x = ch[x][0];else k -= s+1, x = ch[x][1];}}int jump(int a, int b){++a, ++b;int t = a>b, x = kth(a), y = kth(b, x), z = ch[y][t], r = mx[z];ch[y][t] = nil;up(y);join(ch[x][t], z, t^1);return r;}
} T;int main()
{int J;scanf("%d %d", &N, &J);for (int i = 0; i < N; ++i)scanf("%d", &a[i]);T.build();while (J--) {int a, b;char o;scanf("%d %c %d", &a, &o, &b);printf("%d\n", T.jump(a, a+(o == 'D' ? b+1 : -b-1)));}return 0;
}