[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 = , inf = <<;
int N, a[MAX_N];

struct Splay {
    static const int n = MAX_N+, nil = n-;
    int ptr, &root, ch[n][], fa[n], sz[n], v[n], mx[n];
    int type(int x) { return x == ch[fa[x]][]; }
    void up(int x) { sz[x] = sz[ch[x][]] + sz[ch[x][]] + ; mx[x] = std::max(v[x], std::max(mx[ch[x][]], mx[ch[x][]])); }
    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^]);
        set(y, d^, x);
        up(x);
        up(y);
    }
    void splay(int x, int p=)
    {
        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);
                else
                    rot(y, t1), rot(z, t2);
            } else
                rot(y, t1);
        }
    }
    int new_node(int c)
    {
        ch[ptr][] = ch[ptr][] = nil;
        sz[ptr] = ;
        v[ptr] = mx[ptr] = c;
        return ptr++;
    }
    Splay(): ptr(), root(ch[][])
    {
        sz[nil] = ;
        v[nil] = mx[nil] = -inf;
        set(, , new_node());
        set(, , new_node());
    }
    void build()
    {
        build(, N-, , );
        up();
        up();
    }
    void build(int l, int r, int p, int t)
    {
        if (l > r) return;
        int m = (l+r)/, x = new_node(a[m]);
        set(p, t, x);
        build(l, m-, x, );
        build(m+, r, x, );
        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=)
    {
        int x = root;
        while (x != nil) {
            int s = sz[ch[x][]];
            if (k == s+) return splay(x, p), x;
            if (s >= k) x = ch[x][];
            else k -= s+, x = ch[x][];
        }
    }
    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^);
        return r;
    }
} T;

int main()
{
    int J;
    scanf("%d %d", &N, &J);
    for (int i = ; 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+ : -b-)));
    }
    return ;
}