算法笔记--Splay && Link-Cut-Tree

朴灿烈づ我的快乐病毒、 2022-01-12 11:59 153阅读 0赞

**Splay**

参考：[https://tiger0132.blog.luogu.org/slay-notes][https_tiger0132.blog.luogu.org_slay-notes]

普通模板：

const int N = 1e5 + 10;
    int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;
    int n, m;
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    ///区间反转
    inline void push_down(int x) {
        if(lazy[x]) {
            swap(ch[x][0], ch[x][1]);
            lazy[ch[x][0]] ^= 1;
            lazy[ch[x][1]] ^= 1;
            lazy[x] = 0;
        }
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y];
        push_down(y), push_down(x);///区间反转
        int k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        push_down(x);///区间反转
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    void Find(int x) {
        if(!rt) return ;
        int cur = rt;
        while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]];
        Splay(cur);
    }
    void Insert(int x) {
        int cur = rt, p = 0;
        while(cur && val[cur] != x) {
            p = cur;
            cur = ch[cur][x>val[cur]];
        }
        if(cur) cnt[cur]++;
        else {
            cur = ++ncnt;
            if(p) ch[p][x>val[p]] = cur;
            fa[cur] = p;
            ch[cur][0] = ch[cur][1] = 0;
            val[cur] = x;
            cnt[cur] = sz[cur] = 1;
        }
        Splay(cur);
    }
    int Kth(int k) {
        int cur = rt;
        while(true) {
            push_down(cur); ///区间反转
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    inline int get_min(int x) {
        while(x && ch[x][0]) x = ch[x][0];
        return x;
    }
    inline int get_max(int x) {
        while(x && ch[x][1]) x = ch[x][1];
        return x;
    }
    int Pre(int x) {
        Find(x);
        if(val[rt] < x) return rt;
        int cur = ch[rt][0];
        while(ch[cur][1]) cur = ch[cur][1];
        return cur;
    }
    int Succ(int x) {
        Find(x);
        if(val[rt] > x) return rt;
        int cur = ch[rt][1];
        while(ch[cur][0]) cur = ch[cur][0];
        return cur;
    }
    void Remove(int x) {
        int last = Pre(x), next = Succ(x);
        Splay(last), Splay(next, last);
        int del = ch[next][0];
        if(cnt[del] > 1) cnt[del]--, Splay(del);
        else ch[next][0] = 0, push_up(next), push_up(last);
    }
    ///区间反转
    void Reverse(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        lazy[ch[y][0]] ^= 1;
    }
    void Output(int x) {
        push_down(x);
        if(ch[x][0]) Output(ch[x][0]);
        if(1 <= val[x] && val[x] <= n) printf("%d ", val[x]);
        if(ch[x][1]) Output(ch[x][1]);
    }
    void delete_root() {
        if(ch[rt][1]) {
            int cur = ch[rt][1];
            while(cur && ch[cur][0]) cur = ch[cur][0];
            Splay(cur, rt);
            ch[cur][0] = ch[rt][0];
            fa[ch[cur][0]] = cur;
            rt = cur;
        }
        else rt = ch[rt][0];
        fa[rt] = 0;
        if(rt) push_up(rt);
    }
    inline int NewNode(int x) {
        int cur;
        if(q.empty()) cur = ++ncnt;
        else cur = q.front(), q.pop();
        ///初始化
        ch[cur][0] = ch[cur][1] = fa[cur] = lazy[cur] = 0;
        val[cur] = x;
        sz[cur] = cnt[cur] = 1;
        return cur;
    }
    void Recycle(int x) {
        if(ch[x][0]) Recycle(ch[x][0]);
        if(ch[x][1]) Recycle(ch[x][1]);
        if(x) q.push(x);
    }
    int build(int l, int r, int *a) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(a[mid]);
        if(l == r) return cur;
        if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;
        if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    inline void init() {
        ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = lazy[0] = 0;
    }

按排名插入模板（常数较小？？？也许以前的方法写搓了）：

inline void Newnode(int &cur, int f, int a) {
        cur = ++ncnt;
        fa[cur] = f;
        val[cur] = a;
        ch[cur][0] = ch[cur][1] = 0;
        sz[cur] = cnt[cur] = 1;
    }
    void Insert(int x, int y) {
        int p = 0;
        if(!rt) {
            Newnode(rt, 0, y);
            return ;
        }
        if(!x) {
            p = rt;
            sz[p]++;
            while(ch[p][0]) p = ch[p][0], sz[p]++;
            Newnode(ch[p][0], p, y);
            Splay(ch[p][0]);
            return ;
        }
        int u = Kth(x);
        Splay(u);
        Newnode(rt, 0, y);
        ch[rt][1] = ch[u][1];
        fa[ch[rt][1]] = rt;
        ch[u][1] = 0;
        ch[rt][0] = u;
        fa[u] = rt;
        push_up(u), push_up(rt);
    }

例题：

[P3369 【模板】普通平衡树][P3369]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[P3391 【模板】文艺平衡树（Splay）][P3391 _Splay]

思路：跟区间反转相关的Splay维护的都是下标

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[P2042 \[NOI2005\]维护数列][P2042 _NOI2005]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<bits/stdc++.h>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 1e6 + 10;
    int ch[N][2], val[N], cnt[N], fa[N], sz[N], rev[N], lazy[N], ncnt = 0, rt = 0;
    int n, m, a[N], lmx[N], rmx[N], mx[N], sm[N];
    queue<int> q;
    inline int NewNode(int x) {
        int cur;
        if(q.empty()) cur = ++ncnt;
        else cur = q.front(), q.pop();
        ch[cur][0] = ch[cur][1] = fa[cur] = 0;
        rev[cur] = lazy[cur] = 0;
        sz[cur] = cnt[cur] = 1;
        mx[cur] = sm[cur] = val[cur] = x;
        lmx[cur] = rmx[cur] = max(0, x);
        return cur;
    }
    void Recycle(int x) {
        if(ch[x][0]) Recycle(ch[x][0]);
        if(ch[x][1]) Recycle(ch[x][1]);
        if(x) q.push(x);
    }
    inline void push_up(int x) {
        int l = ch[x][0], r = ch[x][1];
        sz[x] = sz[l] + cnt[x] + sz[r];
        sm[x] = sm[l] + val[x] + sm[r];
        lmx[x] = max(lmx[l], sm[l] + val[x] + lmx[r]);
        rmx[x] = max(rmx[r], sm[r] + val[x] + rmx[l]);
        mx[x] = max(rmx[l] + val[x] + lmx[r], max(mx[l], mx[r]));
    }
    inline void push_down(int x) {
        int l = ch[x][0], r = ch[x][1];
        if(lazy[x]) {
            lazy[x] = rev[x] = 0;
            if(l) {
                lazy[l] = 1;
                val[l] = val[x];
                sm[l] = val[l] * sz[l];
                lmx[l] = rmx[l] = max(0, sm[l]);
                mx[l] = sm[l] > 0 ? sm[l] : val[l];
            }
            if(r) {
                lazy[r] = 1;
                val[r] = val[x];
                sm[r] = val[r] * sz[r];
                lmx[r] = rmx[r] = max(0, sm[r]);
                mx[r] = sm[r] > 0 ? sm[r] : val[r];
            }
        }
        if(rev[x]) {
            rev[l] ^= 1, rev[r] ^= 1, rev[x] = 0;
            swap(lmx[l], rmx[l]);
            swap(lmx[r], rmx[r]);
            swap(ch[l][0], ch[l][1]);
            swap(ch[r][0], ch[r][1]);
        }
    
    }
    int build(int l, int r, int *a) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(a[mid]);
        if(l == r) return cur;
        if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;
        if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    int Kth(int k) {
        int cur = rt;
        while(true) {
            push_down(cur); ///区间反转
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    ///区间反转
    void Reverse(int x, int y) {
        int u = Kth(x), v = Kth(x+y+1);
        Splay(u), Splay(v, u);
        int son = ch[v][0];
        if(!lazy[son]) {
            rev[son] ^= 1;
            swap(ch[son][0], ch[son][1]);
            swap(lmx[son], rmx[son]);
        }
        push_up(v), push_up(u);
    }
    void Insert(int x, int y) {
        for (int i = 1; i <= y; ++i) scanf("%d", &a[i]);
        int u = Kth(x+1), v = Kth(x+2);
        Splay(u), Splay(v, u);
        int cur = build(1, y, a);
        ch[v][0] = cur, fa[cur] = v;
        push_up(v), push_up(u);
    }
    void Delete(int x, int y) {
        int u = Kth(x), v = Kth(x+y+1);
        Splay(u), Splay(v, u);
        Recycle(ch[v][0]);
        ch[v][0] = 0;
        push_up(v), push_up(u);
    }
    void Make_Same(int x, int y, int z) {
        int u = Kth(x), v = Kth(x+y+1);
        Splay(u), Splay(v, u);
        int son = ch[v][0];
        lazy[son] = 1;
        val[son] = z;
        sm[son] = z*sz[son];
        mx[son] = sm[son] > 0 ? sm[son] : val[son];
        lmx[son] = rmx[son] = max(0, sm[son]);
        push_up(v), push_up(u);
    }
    int Get_Sum(int x, int y) {
        int u = Kth(x), v = Kth(x+y+1);
        Splay(u), Splay(v, u);
        push_up(v), push_up(u);
        return sm[ch[v][0]];
    }
    char opt[20];
    int x, y, z;
    int main() {
        scanf("%d %d", &n, &m);
        for (int i = 2; i <= n+1; ++i) scanf("%d", &a[i]);
        a[1] = a[n+2] = mx[0] = -2000;
        rt = build(1, n+2, a);
        for (int i = 0; i < m; ++i) {
            scanf("%s", opt);
            if(opt[0] == 'I') {
                scanf("%d %d", &x, &y);
                Insert(x, y);
            }
            else if(opt[0] == 'D') {
                scanf("%d %d", &x, &y);
                Delete(x, y);
            }
            else if(opt[0] == 'M' && opt[5] == 'S') {
                scanf("%d %d %d", &x, &y, &z);
                Make_Same(x, y, z);
            }
            else if(opt[0] == 'R') {
                scanf("%d %d", &x, &y);
                Reverse(x, y);
            }
            else if(opt[0] == 'G') {
                scanf("%d %d", &x, &y);
                printf("%d\n", Get_Sum(x, y));
            }
            else printf("%d\n", mx[rt]);
        }
        return 0;
    }

[POJ 3481][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<cstdio>
    #include<iostream>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    
    const int N = 1e6 + 10;
    int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;
    int a[N];
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    void Find(int x) {
        if(!rt) return ;
        int cur = rt;
        while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]];
        Splay(cur);
    }
    void Insert(int x, int id) {
        int cur = rt, p = 0;
        while(cur && val[cur] != x) {
            p = cur;
            cur = ch[cur][x>val[cur]];
        }
        if(cur) cnt[cur]++;
        else {
            cur = ++ncnt;
            if(p) ch[p][x>val[p]] = cur;
            fa[cur] = p;
            ch[cur][0] = ch[cur][1] = 0;
            val[cur] = x;
            a[cur] = id;
            cnt[cur] = sz[cur] = 1;
        }
        Splay(cur);
    }
    int Kth(int k) {
        int cur = rt;
        while(true) {
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    int Pre(int x) {
        Find(x);
        if(val[rt] < x) return rt;
        int cur = ch[rt][0];
        while(ch[cur][1]) cur = ch[cur][1];
        return cur;
    }
    int Succ(int x) {
        Find(x);
        if(val[rt] > x) return rt;
        int cur = ch[rt][1];
        while(ch[cur][0]) cur = ch[cur][0];
        return cur;
    }
    void Remove(int x) {
        int last = Pre(x), next = Succ(x);
        Splay(last), Splay(next, last);
        int del = ch[next][0];
        if(cnt[del] > 1) cnt[del]--, Splay(del);
        else ch[next][0] = 0, push_up(next), push_up(last);
    }
    int ty, k, p;
    int main() {
        int now = 0;
        Insert(-100, 0);
        Insert(10000010, 0);
        while(~scanf("%d", &ty) && ty) {
            if(ty == 1) {
                scanf("%d %d", &k, &p);
                Insert(p, k);
                ++now;
            }
            else if(ty == 2) {
                if(!now) {
                    printf("0\n");
                    continue;
                }
                int cur = Kth(now+1);
                printf("%d\n", a[cur]);
                --now;
                Remove(val[cur]);
            }
            else if(ty == 3) {
                if(!now) {
                    printf("0\n");
                    continue;
                }
                int cur = Kth(2);
                printf("%d\n", a[cur]);
                --now;
                Remove(val[cur]);
            }
        }
        return 0;
    }

[POJ 2828][]

Splay代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<iostream>
    #include<cstdio>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 2e5 + 10;
    int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;
    int n, m, a[N];
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    
    inline int Kth(int k) {
        int cur = rt;
        while(true) {
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    inline void Newnode(int &cur, int f, int a) {
        cur = ++ncnt;
        fa[cur] = f;
        val[cur] = a;
        ch[cur][0] = ch[cur][1] = 0;
        sz[cur] = cnt[cur] = 1;
    }
    void Insert(int x, int y) {
        int p = 0;
        if(!rt) {
            Newnode(rt, 0, y);
            return ;
        }
        if(!x) {
            p = rt;
            sz[p]++;
            while(ch[p][0]) p = ch[p][0], sz[p]++;
            Newnode(ch[p][0], p, y);
            Splay(ch[p][0]);
            return ;
        }
        int u = Kth(x);
        Splay(u);
        Newnode(rt, 0, y);
        ch[rt][1] = ch[u][1];
        fa[ch[rt][1]] = rt;
        ch[u][1] = 0;
        ch[rt][0] = u;
        fa[u] = rt;
        push_up(u), push_up(rt);
    }
    
    void Output(int x) {
        if(ch[x][0]) Output(ch[x][0]);
        printf("%d ", val[x]);
        if(ch[x][1]) Output(ch[x][1]);
    }
    int x, y;
    int main() {
       while(~scanf("%d", &n)) {
            ncnt = rt = 0;
            for (int i = 1; i <= n; ++i) {
                scanf("%d %d", &x, &y);
                Insert(x, y);
            }
            Output(rt);
            printf("\n");
        }
        return 0;
    }

树状数组代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 4e5 + 5;
    int n, bit[N], res[N];
    pii a[N];
    void add(int x, int a) {
        while(x <= n) bit[x] += a, x += x&-x;
    }
    int Kth(int k) {
        int up = log(n)/log(2);
        int res = 0;
        for (int i = up; i >= 0; --i) {
            if(res + (1<<i) > n) continue;
            if(bit[res+(1<<i)] < k) {
                res += 1<<i;
                k -= bit[res];
            }
        }
        return res+1;
    }
    int main() {
        while(~scanf("%d", &n)) {
            for (int i = 1; i <= n; ++i) add(i, 1);
            for (int i = 1; i <= n; ++i) scanf("%d %d", &a[i].fi, &a[i].se);
            for (int i = n; i >= 1; --i) {
                int pos = Kth(a[i].fi+1);
                res[pos] = a[i].se;
                add(pos, -1);
            }
            for (int i = 1; i <= n; ++i) printf("%d%c", res[i], " \n"[i==n]);
            for (int i = 0; i <= n; ++i) bit[i] = 0;
        }
        return 0;
    }

[HDU 1890][]

思路：按下标建树，每次将要翻转到前面的节点Splay到根上，将它的左儿子打上标记，然后把根删掉。

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[HDU 3436][]

思路：先把TOP操作和QUERY操作的值单独扣出来，然后其他的一段区间看成一个节点

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<cstdio>
    #include<iostream>
    #include<vector>
    #include<unordered_map>
    #include<algorithm>
    #include<cmath>
    #include<cstring>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdi pair<double, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 2e5 + 1000;
    int ch[N][2], st[N], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;
    int n, m;
    int T, op[N/2], a[N/2], node[N], tot, vc[N/2], tmp;
    pii t[N];
    char s[100];
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    inline int Kth(int k) {
        int cur = rt;
        while(true) {
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    inline int KTH(int k) {
        int cur = rt;
        while(true) {
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return st[cur] + k-sz[ch[cur][0]]-1;
        }
    }
    inline void delete_root() {
        if(ch[rt][1]) {
            int cur = ch[rt][1];
            while(cur && ch[cur][0]) cur = ch[cur][0];
            Splay(cur, rt);
            ch[cur][0] = ch[rt][0];
            fa[ch[cur][0]] = cur;
            rt = cur;
        }
        else rt = ch[rt][0];
        fa[rt] = 0;
        if(rt) push_up(rt);
    }
    inline int NewNode(pii x) {
        int cur = ++ncnt;
        ch[cur][0] = ch[cur][1] = fa[cur] = 0;
        st[cur] = x.fi;
        cnt[cur] = sz[cur] = x.se - x.fi + 1;
        return cur;
    }
    int build(int l, int r) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(t[mid]);
        node[mid] = cur;
        if(l == r) return cur;
        ch[cur][0] = build(l, mid-1); if(ch[cur][0]) fa[ch[cur][0]] = cur;
        ch[cur][1] = build(mid+1, r); if(ch[cur][1]) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    inline int get(int x) {
        int l = 1, r = tot, m = l+r >> 1;
        while(l <= r) {
            if(t[m].fi > x) r = m-1;
            else if(t[m].se < x) l = m+1;
            else return node[m];
            m = l+r >> 1;
        }
    }
    inline void init() {
        tmp = 1;
        tot = 0;
        ncnt = rt = 0;
        ch[0][0] = ch[0][1] = st[0] = cnt[0] = fa[0] = sz[0] = 0;
    }
    int main() {
    //    freopen("in.txt", "r", stdin);
    //    freopen("out.txt", "w", stdout);
        scanf("%d", &T);
        for (int cs = 1; cs <= T; ++cs) {
            init();
            scanf("%d %d", &n, &m);
            for (int i = 1; i <= m; ++i) {
                scanf("%s%d", s, &a[i]);
                if(s[0] == 'T') op[i] = 1, vc[tmp++] = a[i];
                else if(s[0] == 'Q') op[i] = 2, vc[tmp++] = a[i];
                else op[i] = 3;
            }
            vc[tmp++] = n;
            sort(vc, vc+tmp);
            tmp = unique(vc, vc+tmp) - vc;
            for (int i = 1; i < tmp; ++i) {
                if(vc[i]-vc[i-1] > 1) t[++tot].fi = vc[i-1]+1, t[tot].se = vc[i]-1;
                t[++tot].fi = vc[i], t[tot].se = vc[i];
            }
            rt = build(1, tot);
            printf("Case %d:\n", cs);
            for (int i = 1; i <= m; ++i) {
                if(op[i] == 1) {
                    int cur = get(a[i]);
                    Splay(cur);
                    delete_root();
                    int now = rt;
                    while(now && ch[now][0]) now = ch[now][0];
                    ch[now][0] = cur;
                    fa[cur] = now;
                    st[cur] = a[i];
                    sz[cur] = cnt[cur] = 1;
                    ch[cur][0] = ch[cur][1] = 0;
                    Splay(cur);
                }
                else if(op[i] == 2) {
                    int cur = get(a[i]);
                    Splay(cur);
                    printf("%d\n", sz[ch[cur][0]]+1);
                }
                else printf("%d\n", KTH(a[i]));
            }
        }
        return 0;
    }

[HDU 3487][]

思路：常规操作

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[HYSBZ 1208][]

思路：平衡树

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<climits>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdi pair<double, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 1e5 + 10;
    const int MOD = 1e6;
    struct splay {
        int ch[N][2], cnt[N], fa[N], sz[N], ncnt, rt;
        int n, m;
        LL val[N];
        inline int ck(int x) {
            return ch[fa[x]][1] == x;
        }
        inline void push_up(int x) {
            sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
        }
        void Rotate(int x) {
            int y = fa[x], z = fa[y];
            int k = ck(x), w = ch[x][k^1];
            ch[y][k] = w, fa[w] = y;
            ch[z][ck(y)] = x, fa[x] = z;
            ch[x][k^1] = y, fa[y] = x;
            push_up(y), push_up(x);
        }
        void Splay(int x, int goal = 0) {
            while(fa[x] != goal) {
                int y = fa[x], z = fa[y];
                if(z != goal) {
                    if(ck(x) == ck(y)) Rotate(y);
                    else Rotate(x);
                }
                Rotate(x);
            }
            if(!goal) rt = x;
        }
        void Find(LL x) {
            if(!rt) return ;
            int cur = rt;
            while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]];
            Splay(cur);
        }
        void Insert(LL x) {
            int cur = rt, p = 0;
            while(cur && val[cur] != x) {
                p = cur;
                cur = ch[cur][x>val[cur]];
            }
            if(cur) cnt[cur]++;
            else {
                cur = ++ncnt;
                if(p) ch[p][x>val[p]] = cur;
                fa[cur] = p;
                ch[cur][0] = ch[cur][1] = 0;
                val[cur] = x;
                cnt[cur] = sz[cur] = 1;
            }
            Splay(cur);
        }
        int Kth(int k) {
            int cur = rt;
            while(true) {
                if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
                else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
                else return cur;
            }
        }
        int Pre(LL x) {
            Find(x);
            if(val[rt] < x) return rt;
            int cur = ch[rt][0];
            while(ch[cur][1]) cur = ch[cur][1];
            return cur;
        }
        int Succ(LL x) {
            Find(x);
            if(val[rt] > x) return rt;
            int cur = ch[rt][1];
            while(ch[cur][0]) cur = ch[cur][0];
            return cur;
        }
        int pre(LL x) {
            Find(x);
            if(val[rt] <= x) return rt;
            int cur = ch[rt][0];
            while(ch[cur][1]) cur = ch[cur][1];
            return cur;
        }
        int succ(LL x) {
            Find(x);
            if(val[rt] >= x) return rt;
            int cur = ch[rt][1];
            while(ch[cur][0]) cur = ch[cur][0];
            return cur;
        }
        void Remove(LL x) {
            int last = Pre(x), next = Succ(x);
            Splay(last), Splay(next, last);
            int del = ch[next][0];
            if(cnt[del] > 1) cnt[del]--, Splay(del);
            else ch[next][0] = 0, push_up(next), push_up(last);
        }
        inline int NewNode(LL x) {
            int cur = ++ncnt;
            ch[cur][0] = ch[cur][1] = fa[cur] = 0;
            val[cur] = x;
            sz[cur] = cnt[cur] = 1;
            return cur;
        }
        inline void init() {
            ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = 0;
        }
    }t1, t2;
    int T, a, b;
    int main() {
        scanf("%d", &T);
        t1.init();
        t2.init();
        t1.Insert(LONG_MIN);
        t1.Insert(LONG_MAX);
        t2.Insert(LONG_MIN);
        t2.Insert(LONG_MAX);
        LL ans = 0;
        while(T--) {
            scanf("%d %d", &a, &b);
            if(a == 0) {
                if(t2.sz[t2.rt] == 2) t1.Insert(b);
                else {
                    LL del, tmp = LONG_MAX;
                    LL pre = t2.val[t2.pre(b)];
                    if(pre != LONG_MIN && abs(pre - b) < tmp) {
                        tmp = abs(pre-b);
                        del = pre;
                    }
                    LL succ = t2.val[t2.succ(b)];
                    if(succ != LONG_MAX && abs(succ - b) < tmp) {
                        tmp = abs(succ-b);
                        del = succ;
                    }
                    (ans += tmp) %= MOD;
                    t2.Remove(del);
                }
            }
            else {
                if(t1.sz[t1.rt] == 2) t2.Insert(b);
                else {
                    LL del, tmp = LONG_MAX;
                    LL pre = t1.val[t1.pre(b)];
                    if(pre != LONG_MIN && abs(pre - b) < tmp) {
                        tmp = abs(pre-b);
                        del = pre;
                    }
                    LL succ = t1.val[t1.succ(b)];
                    if(succ != LONG_MAX && abs(succ - b) < tmp) {
                        tmp = abs(succ-b);
                        del = succ;
                    }
                    (ans += tmp) %= MOD;
                    t1.Remove(del);
    
                }
            }
        }
        printf("%lld\n", ans);
        return 0;
    }

[HYSBZ 1269][]

思路：常规操作，一开始数据范围看错，一直RE

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<climits>
    #include<string>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdi pair<double, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 2.2e6;
    int ch[N][2], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;
    char val[N], s[100];
    string t;
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    ///区间反转
    inline void push_down(int x) {
        if(lazy[x]) {
            swap(ch[x][0], ch[x][1]);
            lazy[ch[x][0]] ^= 1;
            lazy[ch[x][1]] ^= 1;
            lazy[x] = 0;
        }
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y];
        push_down(y), push_down(x);///区间反转
        int k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        push_down(x);///区间反转
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    void Insert(char x) {
        int cur = rt, p = 0;
        while(cur && val[cur] != x) {
            p = cur;
            cur = ch[cur][x>val[cur]];
        }
        if(cur) cnt[cur]++;
        else {
            cur = ++ncnt;
            if(p) ch[p][x>val[p]] = cur;
            fa[cur] = p;
            ch[cur][0] = ch[cur][1] = 0;
            val[cur] = x;
            cnt[cur] = sz[cur] = 1;
        }
        Splay(cur);
    }
    int Kth(int k) {
        int cur = rt;
        while(true) {
            push_down(cur); ///区间反转
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    inline int NewNode(char x) {
        int cur = ++ncnt;
        ch[cur][0] = ch[cur][1] = fa[cur] = lazy[cur] = 0;
        val[cur] = x;
        sz[cur] = cnt[cur] = 1;
        return cur;
    }
    void Reverse(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        lazy[ch[y][0]] ^= 1;
    }
    void Delete(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        ch[y][0] = 0;
        push_up(y), push_up(x);
    }
    int build(int l, int r, string &a) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(a[mid]);
        if(l == r) return cur;
        if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;
        if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    void Insert(int x, int n) {
        int u = Kth(x), v = Kth(x+1);
        Splay(u), Splay(v, u);
        int cur = build(0, n-1, t);
        fa[cur] = v;
        ch[v][0] = cur;
        push_up(v), push_up(u);
        Splay(cur);
    }
    inline void init() {
        ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = lazy[0] = 0;
    }
    int T, n, k, a, b, now = 0;
    int main() {
        init();
        Insert('#');
        Insert('*');
        cin >> T;
        for (int i = 0; i < T; ++i) {
            cin >> s;
             if(s[0] == 'M') {
                cin >> k;
                now = k;
            }
            else if(s[0] == 'I') {
                cin >> n;
                cin.ignore();
                getline(cin, t);
                Insert(now+1, n);
            }
            else if(s[0] == 'D') {
                cin >> n;
                Delete(now+1, now+n);
            }
            else if(s[0] == 'R') {
                cin >> n;
                Reverse(now+1, now+n);
            }
            else if(s[0] == 'G') {
                char t = val[Kth(now+2)];
                if(t != '\n') putchar(t);
                putchar('\n');
            }
            else if(s[0] == 'P') --now;
            else if(s[0] == 'N') ++now;
        }
        return 0;
    }

[POJ 3580][]

思路：常规操作，REVOLVE记得取模，这个很坑

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #pragma GCC optimize(4)
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<climits>
    #include<string>
    using namespace std;
    #define y1 y11
    #define fi first
    #define se second
    #define pi acos(-1.0)
    #define LL long long
    //#define mp make_pair
    #define pb push_back
    #define ls rt<<1, l, m
    #define rs rt<<1|1, m+1, r
    #define ULL unsigned LL
    #define pll pair<LL, LL>
    #define pli pair<LL, int>
    #define pii pair<int, int>
    #define piii pair<pii, int>
    #define pdi pair<double, int>
    #define pdd pair<double, double>
    #define mem(a, b) memset(a, b, sizeof(a))
    #define debug(x) cerr << #x << " = " << x << "\n";
    #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //head
    
    const int N = 2e5 + 10;
    int ch[N][2], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;
    LL val[N], a[N], tree[N], add[N];
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        int l = ch[x][0], r = ch[x][1];
        tree[x] = min(val[x], min(tree[l], tree[r]));
        sz[x] = sz[l] + sz[r] + cnt[x];
    }
    ///区间反转
    inline void push_down(int x) {
        int l = ch[x][0], r = ch[x][1];
        if(lazy[x]) {
            swap(ch[x][0], ch[x][1]);
            if(l) lazy[l] ^= 1;
            if(r) lazy[r] ^= 1;
            lazy[x] = 0;
        }
        if(add[x]) {
            if(l) val[l] += add[x], tree[l] += add[x], add[l] += add[x];
            if(r) val[r] += add[x], tree[r] += add[x], add[r] += add[x];
            add[x] = 0;
        }
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y];
        push_down(y), push_down(x);///区间反转
        int k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        push_down(x);///区间反转
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    
    int Kth(int k) {
        int cur = rt;
        while(true) {
            push_down(cur); ///区间反转
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    inline int NewNode(LL x) {
        int cur = ++ncnt;
        ch[cur][0] = ch[cur][1] = fa[cur] = add[cur] = lazy[cur] = 0;
        val[cur] = x;
        tree[cur] = x;
        sz[cur] = cnt[cur] = 1;
        return cur;
    }
    ///区间反转
    void REVERSE(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        int cur = ch[y][0];
        lazy[cur] ^= 1;
    }
    void ADD(int l, int r, LL z) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        val[ch[y][0]] += z;
        tree[ch[y][0]] += z;
        add[ch[y][0]] += z;
        push_up(y), push_up(x);
    }
    void REVOLVE(int l, int r, int z) {
        int len = r-l+1;
        z = (z%len + len) % len;
        if(!z) return ;
        int ll = r-z+1, rr = r;
        int x = Kth(ll), y = Kth(rr+2);
        Splay(x), Splay(y, x);
        int cur = ch[y][0];
        ch[y][0] = 0;
        push_up(y), push_up(x);
        x = Kth(l), y = Kth(l+1);
        Splay(x), Splay(y, x);
        ch[y][0] = cur;
        fa[cur] = y;
        push_up(y), push_up(x);
        Splay(cur);
    }
    LL MIN(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        return tree[ch[y][0]];
    }
    void INSERT(int x, LL y) {
        int u = Kth(x+1), v = Kth(x+2);
        Splay(u), Splay(v, u);
        int cur = NewNode(y);
        fa[cur] = v;
        ch[v][0] = cur;
        push_up(v), push_up(u);
    }
    void DELETE(int x) {
        int u = Kth(x), v = Kth(x+2);
        Splay(u), Splay(v, u);
        ch[v][0] = 0;
        push_up(v), push_up(u);
    }
    int build(int l, int r, LL *a) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(a[mid]);
        if(l == r) return cur;
        if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;
        if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    inline void init() {
        ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = add[0] = lazy[0] = 0;
        tree[0] = LONG_MAX;
    }
    int n, m, x, y;
    LL z;
    char s[100];
    int main() {
        init();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        a[0] = a[n+1] = LONG_MAX;
        rt = build(0, n+1, a);
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i) {
            scanf("%s", s);
            if(s[0] == 'A') {
                scanf("%d %d %lld", &x, &y, &z);
                ADD(x, y, z);
            }
            else if(s[0] == 'R' && s[3] == 'E') {
                scanf("%d %d", &x, &y);
                REVERSE(x, y);
            }
            else if(s[0] == 'R' && s[3] == 'O') {
                scanf("%d %d %lld", &x, &y, &z);
                REVOLVE(x, y, z);
            }
            else if(s[0] == 'I') {
                scanf("%d %d", &x, &y);
                INSERT(x, y);
            }
            else if(s[0] == 'D') {
                scanf("%d", &x);
                DELETE(x);
            }
            else if(s[0] == 'M') {
                scanf("%d %d", &x, &y);
                printf("%lld\n", MIN(x, y));
            }
        }
        return 0;
    }

[POJ 3468][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<climits>
    #include<cstring>
    using namespace std;
    #define LL long long
    
    const int N = 1e5 + 10;
    int ch[N][2], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;
    LL add[N], tree[N], val[N], a[N];
    inline int ck(int x) {
        return ch[fa[x]][1] == x;
    }
    inline void push_up(int x) {
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
        tree[x] = val[x] + tree[ch[x][0]] + tree[ch[x][1]];
    }
    ///区间反转
    inline void push_down(int x) {
        if(add[x]) {
            int l = ch[x][0], r = ch[x][1];
            if(l) add[l] += add[x], val[l] += add[x], tree[l] += sz[l]*1LL*add[x];
            if(r) add[r] += add[x], val[r] += add[x], tree[r] += sz[r]*1LL*add[x];
            add[x] = 0;
        }
    }
    void Rotate(int x) {
        int y = fa[x], z = fa[y];
        push_down(y), push_down(x);///区间反转
        int k = ck(x), w = ch[x][k^1];
        ch[y][k] = w, fa[w] = y;
        ch[z][ck(y)] = x, fa[x] = z;
        ch[x][k^1] = y, fa[y] = x;
        push_up(y), push_up(x);
    }
    void Splay(int x, int goal = 0) {
        push_down(x);///区间反转
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            if(z != goal) {
                if(ck(x) == ck(y)) Rotate(y);
                else Rotate(x);
            }
            Rotate(x);
        }
        if(!goal) rt = x;
    }
    int Kth(int k) {
        int cur = rt;
        while(true) {
            push_down(cur); ///区间反转
            if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];
            else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];
            else return cur;
        }
    }
    void ADD(int l, int r, LL c) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        add[ch[y][0]] += c;
        tree[ch[y][0]] += sz[ch[y][0]]*1LL*c;
        val[ch[y][0]] += c;
        push_up(y), push_up(x);
    }
    LL SUM(int l, int r) {
        int x = Kth(l), y = Kth(r+2);
        Splay(x), Splay(y, x);
        return tree[ch[y][0]];
    }
    inline int NewNode(LL x) {
        int cur;cur = ++ncnt;
        ch[cur][0] = ch[cur][1] = fa[cur] = add[cur] = 0;
        val[cur] = x;
        tree[cur] = x;
        sz[cur] = cnt[cur] = 1;
        return cur;
    }
    
    int build(int l, int r, LL *a) {
        if(l > r) return 0;
        int mid = l+r >> 1, cur = NewNode(a[mid]);
        if(l == r) return cur;
        if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;
        if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;
        push_up(cur);
        return cur;
    }
    inline void init() {
        ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = add[0] = tree[0] = 0;
    }
    int n, m, l, r;
    LL c;
    char s[100];
    int main() {
        init();
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
        rt = build(0, n+1, a);
        for (int i = 1; i <= m; ++i) {
            scanf("%s", s);
            if(s[0] == 'Q') {
                scanf("%d %d", &l, &r);
                printf("%lld\n", SUM(l, r));
            }
            else if(s[0] == 'C') {
                scanf("%d %d %lld", &l, &r, &c);
                ADD(l, r, c);
            }
        }
        return 0;
    }

[HDU 2475][]

将树按入时间戳和出时间戳变成线性结构，然后在这个线性结构上用splay维护

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

易错点：

1.修改后记得push\_up

2.一直往左子树或右子树走时记得第一步判当前节点是不是0

**套板子一时爽，一直套一直爽**

**Link-Cut-Tree**

模板：

const int N = 3e5 + 5;
    int f[N],v[N],s[N],r[N],hep[N],ch[N][2];
    inline int get(int x){
        return ch[f[x]][0]==x||ch[f[x]][1]==x;
    }
    inline void pushup(int x){
        s[x]=s[ch[x][1]]^s[ch[x][0]]^v[x];
    }
    inline void filp(int x){
        swap(ch[x][0],ch[x][1]);r[x]^=1;
    }
    inline void pushdown(int x){
        if(!r[x])return;r[x]=0;
        if(ch[x][0])filp(ch[x][0]);
        if(ch[x][1])filp(ch[x][1]);
    }
    inline void rotate(int x){
        int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k];
        if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;
        if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
    }
    inline void Splay(int x){
        int y=x,top=0;hep[++top]=y;
        while(get(y))hep[++top]=y=f[y];
        while(top)pushdown(hep[top--]);
        while(get(x)){
            y=f[x],top=f[y];
            if(get(y))
               rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);
            rotate(x);
        }pushup(x);return;
    }
    inline void Access(int x){
        for(register int y=0;x;x=f[y=x])
           Splay(x),ch[x][1]=y,pushup(x);
    }
    inline void makeroot(int x){
        Access(x);Splay(x);filp(x);
    }
    inline int findroot(int x){
        Access(x);Splay(x);
        while(ch[x][0])pushdown(x),x=ch[x][0];
        return x;
    }
    inline void split(int x,int y){
        makeroot(x);Access(y);Splay(y);
    }
    inline void link(int x,int y){
        makeroot(x);if(findroot(y)!=x)f[x]=y;
    }
    inline void cut(int x,int y){
        split(x,y);
        if(findroot(y)==x&&f[x]==y&&!ch[x][1]){
            f[x]=ch[y][0]=0;pushup(y);
        }return;
    }

[P3690 【模板】Link Cut Tree （动态树）][P3690 _Link Cut Tree]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[HYSBZ 1036][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[HDU 4010][]

思路：注意cut和普通的cut不一样

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[URAL 1553][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[SPOJ OTOCI][]

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

转载于:https://www.cnblogs.com/widsom/p/10604057.html

[https_tiger0132.blog.luogu.org_slay-notes]: https://tiger0132.blog.luogu.org/slay-notes
[P3369]: https://www.luogu.org/problemnew/show/P3369
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220109/1e4bca7d284a432e8bfb99274a37041d.png
[P3391 _Splay]: https://www.luogu.org/problemnew/show/P3391
[P2042 _NOI2005]: https://www.luogu.org/problemnew/show/P2042
[POJ 3481]: https://cn.vjudge.net/problem/15084/origin
[POJ 2828]: https://cn.vjudge.net/problem/10345/origin
[HDU 1890]: https://cn.vjudge.net/problem/19564/origin
[HDU 3436]: https://cn.vjudge.net/problem/10828/origin
[HDU 3487]: https://cn.vjudge.net/problem/10388/origin
[HYSBZ 1208]: https://cn.vjudge.net/problem/26192/origin
[HYSBZ 1269]: https://cn.vjudge.net/problem/26195/origin
[POJ 3580]: https://cn.vjudge.net/problem/11124/origin
[POJ 3468]: https://cn.vjudge.net/problem/14607/origin
[HDU 2475]: https://cn.vjudge.net/problem/13414/origin
[P3690 _Link Cut Tree]: https://www.luogu.org/problemnew/show/P3690
[HYSBZ 1036]: https://cn.vjudge.net/problem/24279/origin
[HDU 4010]: https://cn.vjudge.net/problem/23014/origin
[URAL 1553]: https://cn.vjudge.net/problem/20483/origin
[SPOJ OTOCI]: https://cn.vjudge.net/problem/18141/origin