【Splay 模闆題】HDU 3587 BZOJ 1251

Step1 Problem:

HDU 3587

輸入給出長 n 的一個序列，進行m次操作

1. 把序列中的第 a 個數字到第 b 個數字取出來插入到第 c 個數字後面

2. 翻轉序列的 第 a 個數字到第 b 個數字這個區間

所有操作後輸出結果

n <= 1e5 , m<=1e5

BZOJ 1251

輸入給出長 n 的一個序列，進行m次操作

1. 把 [L, R] 這個區間的數都加上 V

2. 把 [L, R] 這個區間翻轉

3. 求 [L, R] 這個區間的數的最值

n < 5e4，m<1e5

Step2 Ideas:

金桔的闆子，東慶的注釋，我就改了一點細微的格式，比較适合自己。

Step3 Code:

#include<bits/stdc++.h>
using namespace std;
const int N = +;
//用來處理區間詢問，每個節點維護的是一個子樹的資訊
//Splay可以将一段連續區間内的節點放到一顆子樹内，是以這樣可以維護一段區間的資訊
struct Info {
    int siz;
    int ma;
    Info(){};
    Info(int x) {
        siz = ;
        ma = x;
    }
    void addIt(int x) {
        ma += x;
    }
};
//區間（子樹）資訊的合并
Info operator+(const Info &l, const Info &r)
{
    Info ret;
    ret.siz = l.siz + r.siz;
    ret.ma = max(l.ma, r.ma);
    return ret;
}
int root;
//Splay的節點
struct node {
    //son[0]是左兒子，son[1]是右兒子
    int son[], fa;
    int val, lazy;
    bool flp;
    Info info;
    int &l() {return son[];}
    int &r() {return son[];}
    node(int v = ) {
        l() = r() = fa = -;
        val = v;
        info = Info(v);
        lazy = ;
        flp = false;
    }
    //修改Splay上的節點後，也需要對 info 的資訊進行維護
    void addIt(int v) {
        val += v;
        lazy += v;
        info.addIt(v);
    }
    void maintain();
    void push_down();
}tree[N];
//進行 pushdown 操作，類似線段樹
void node::push_down() {
    if(lazy != ) {
        if(l() != -) tree[l()].addIt(lazy);
        if(r() != -) tree[r()].addIt(lazy);
        lazy = ;
    }
    if(flp) {
        swap(l(), r());
        if(l() != -) tree[l()].flp ^= ;
        if(r() != -) tree[r()].flp ^= ;
        flp = false;
    }
}
//Splay 進行旋轉操作時，子樹發生了改變，需要重新維護區間（子樹）資訊
void node::maintain() {
    info = Info(val);
    if(l() != -) info = tree[l()].info + info;
    if(r() != -) info = info + tree[r()].info;
}
//查詢目前節點是父親的左兒子還是右兒子，左兒子傳回0，右兒子傳回1，如果無父親傳回-1
int ori(int st) {
    int fa = tree[st].fa;
    if(fa == -) return -;
    return st == tree[fa].r();
}
//把 sn 變成 st 的兒子節點，如果 d 是 0 是左兒子，否則是右兒子
//這裡子樹發生了改變，需要重新維護 info 資訊
void setc(int sn, int st, int d) {
    if(st != -) {
        tree[st].son[d] = sn;
        tree[st].maintain();
    }
    if(sn != -) tree[sn].fa = st;
}
//進行旋轉操作，這裡需要自己畫圖了解一下，這裡包括了左旋和右旋
void zg(int x) {
    int st = tree[x].fa, p = -;
    tree[st].push_down();
    tree[x].push_down();
    int d = ori(x), dst = ori(st);
    if(st != -) p = tree[st].fa;
    setc(tree[x].son[d^], st, d);
    setc(st, x, d^);
    setc(x, p, dst);
}
#define f(x) (tree[x].fa)
//将 x 旋轉成 fa 的兒子，如果将 x 旋轉成 根節點的話則不填 fa
void splay(int x, int fa = -) {
    //循環直到 x 是 fa 的兒子
    while(f(x) != fa) {
        //如果 fa 是 x 的爺爺，那麼隻需要一次旋轉
        if(f(f(x)) == fa) zg(x);
        else {
            //雙旋！
            //說明進行 zig zig 或者 zag zag 旋轉
            if(ori(x) == ori(f(x))) zg(f(x));
            else zg(x);
            zg(x);
        }
    }
    //更新根節點
    if(fa == -) root = x;
}
int value[N];
int pos;
//要保證 value 有序，類似線段樹建樹，這樣樹高是 log(n) 的
int build(int l, int r) {
    int st = pos++;
    int m = (l+r)>>;
    tree[st] = node(value[m]);
    if(l < m) setc(build(l, m-), st, );
    if(r > m) setc(build(m+, r), st, );
    return st;
}
int build(int n) {
    pos = ;
    //添加 0 和 n + 1 兩個虛拟節點，友善 cut 操作
    return build(, n+);
}
//獲得以 st 為根節點，中序周遊的第 v 個節點
int getid(int v, int st) {
    tree[st].push_down();
    int l = tree[st].l();
    int lsiz =  + (l == - ?  : tree[l].info.siz);
    if(v == lsiz) return st;
    int d = v > lsiz;
    if(d) v -= lsiz;
    return getid(v, tree[st].son[d]);
}
int getseg(int l, int r) {
    l--, r++;
    //下标從 0 開始，需要找第 l + 1 個節點
    l = getid(l+, root), r = getid(r+, root);
    //現在 r+1 是 l-1 的父親，那麼 l-r 這一段子樹肯定是 l-1 的右兒子
    splay(r);
    splay(l, r);
    return tree[l].r();
}
void flip(int l, int r) {
    int pos = getseg(l, r);
    tree[pos].flp ^= ;
}
void cut(int l, int r, int idx) {
    //切下來 l - r 這段區間
    int rootson1 = getseg(l, r);
    int father = tree[rootson1].fa;
    setc(-, father, );
    l = idx, r = idx+;
    //因為這裡是虛拟節點，是以要多加一個 1
    l = getid(l+, root);
    r = getid(r+, root);
    //将 idx+1 成為 idx 的父親，那麼上面切下來的區間放到idx的右邊即可
    splay(r);
    splay(l, r);
    setc(rootson1, l, );
}
int n, m;
int ans[N], cnt;
//中序周遊
void dfs(int u)
{
    tree[u].push_down();
    if(tree[u].son[] != -) dfs(tree[u].son[]);
    ans[cnt++] = tree[u].val;
    if(tree[u].son[] != -) dfs(tree[u].son[]);
}
int main()
{
    char op[];
    while(~scanf("%d %d", &n, &m))
    {
        if(n==- && m ==-) break;
        for(int i = ; i <= n; i++) value[i] = i;
        root = build(n);
        int l, r, idx;
        while(m--)
        {
            scanf("%s", op);
            if(op[] == 'C') {
                scanf("%d %d %d", &l, &r, &idx);
                cut(l, r, idx);
            }
            else {
                scanf("%d %d", &l, &r);
                flip(l, r);
            }
        }
        cnt = ;
        dfs(root);
        for(int i = ; i < cnt-; i++)
        {
            if(i > ) printf(" ");
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return ;
}