前不久其實已經(jīng)學(xué)過splay了，但是總覺得似乎不能靈活地改造它，于是重新學(xué)習(xí)了一波。

感謝https://oi.men.ci/splay-notes-1/
關(guān)于splay的解釋這里說的也比較清楚
下面我們分成單點(diǎn)版和區(qū)間版討論

入門題 Tyvj 1728 普通平衡樹

您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標(biāo)題），來維護(hù)一些數(shù)，其中需要提供以下操作：
1. 插入x數(shù)
2. 刪除x數(shù)(若有多個相同的數(shù)，因只刪除一個)
3. 查詢x數(shù)的排名(若有多個相同的數(shù)，因輸出最小的排名)
4. 查詢排名為x的數(shù)
5. 求x的前驅(qū)(前驅(qū)定義為小于x，且最大的數(shù))
6. 求x的后繼(后繼定義為大于x，且最小的數(shù))

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i=a; i<=b; i++)
#define drep(i, a, b) for (int i=b; i>=a; i--)
typedef long long LL;
using namespace std;

struct Splay {
    struct node {
        node *fa, *ch[2], **root;
        int x, size, cnt;
        node(node **root, node *fa, int x): root(root), fa(fa), x(x), cnt(1), size(1) {
            ch[0]=ch[1]=NULL;
        }
        inline int relation() {
            return this == fa->ch[0] ? 0 : 1;
        }
        inline void maintain() {
            size = cnt;
            if (ch[0]) size += ch[0]->size;
            if (ch[1]) size += ch[1]->size;
        }

        void rotate() {
            node *old=fa;
            int r=relation();

            fa=old->fa;
            if (old->fa) old->fa->ch[old->relation()]=this;
            if (ch[r^1]) ch[r^1]->fa=old;
            old->ch[r]=ch[r^1];
            old->fa=this;
            ch[r^1]=old;

            old->maintain();
            maintain();
            if (fa==NULL) *root=this;
        }
        void splay(node *target=NULL) {
            while (fa!=target) {
                if (fa->fa==target) rotate();
                else if (fa->relation()==relation()) {
                    fa->rotate();
                    rotate();
                }else {
                    rotate();
                    rotate();
                }
            }
        }
        node *pred() {
            node *v=ch[0];
            while (v->ch[1]) v=v->ch[1];
            return v;
        }//前驅(qū)precursor
        node *succ() {
            node *v = ch[1];
            while (v->ch[0]) v=v->ch[0];
            return v;
        }

        int rank() {
            return ch[0] ? ch[0]->size : 0;
        }
    } *root;
    Splay():root(NULL) {
        insert(INT_MAX);
        insert(INT_MIN);
    }
    node *insert(int x) {
        node **v = &root, *fa=NULL;
        while (*v!=NULL && (*v)->x!=x) {
            fa=*v;
            fa->size++;
            if (x<fa->x) v=&fa->ch[0]; else v=&fa->ch[1];
        }
        if (*v!=NULL) {
            (*v)->cnt++;
            (*v)->size++;
        }else (*v) = new node(&root, fa, x);
        (*v)->splay();
        return root;
    }
    node *find(int x) {
        node *v=root;
        while (v!=NULL && v->x != x) if (x<v->x) v=v->ch[0]; else v=v->ch[1];
        if (v) v->splay();
        return v;
    }
    void erase(node *v) {
        node *pred=v->pred(), *succ=v->succ();
        pred->splay();
        succ->splay(pred);
        if (v->size>1) {
            v->size--, v->cnt--;
        }else {
            delete succ->ch[0];
            succ->ch[0]=NULL;
        }
        succ->size--, pred->size--;
    }
    void erase(int x) {
        node *v=find(x);
        if (!v) return;
        erase(v);
    }
    int pred(int x) {
        node *v = find(x);
        if (v==NULL) {
            v=insert(x);
            int res=v->pred()->x;
            erase(v);
            return res;
        }else return v->pred()->x;
    }
    int succ(int x) {
        node *v=find(x);
        if (v==NULL) {
            v=insert(x);
            int res=v->succ()->x;
            erase(v);
            return res;
        }else return v->succ()->x;
    }
    int rank(int x) {
        node *v=find(x);
        if (v==NULL) {
            v=insert(x);
            int res=v->rank();
            erase(v);
            return res;
        }else return v->rank();
    }
    int select(int k) {
        node *v = root;
        while (!(k >= v->rank() && k < v->rank() + v->cnt)){
            if (k<v->rank()) v=v->ch[0]; else {
                k-=v->rank()+v->cnt;
                v=v->ch[1];
            }
        }
        v->splay();
        return v->x;
    }
}splay;

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int opt, x;
        scanf("%d %d", &opt, &x);
        if (opt==1) splay.insert(x);
        if (opt==2) splay.erase(x);
        if (opt==3) printf("%d\n", splay.rank(x));
        if (opt==4) printf("%d\n", splay.select(x));
        if (opt==5) printf("%d\n", splay.pred(x));
        if (opt==6) printf("%d\n", splay.succ(x));
    }
    return 0;
}

如果是打acm的話不太懂splay的原理其實沒有太大關(guān)系，這個板子已經(jīng)把splay的基本操作封裝再node結(jié)構(gòu)體里面了，可以理解成splay是一個一直在維護(hù)平衡的名次樹。所以起碼要理解名次樹的性質(zhì)：

左子樹的值<根節(jié)點(diǎn)的值<右子樹的值

上面的splay只支持單點(diǎn)操作，其實用線段樹也可以實現(xiàn)（強(qiáng)烈推薦zkw的論文《統(tǒng)計的力量》，很精妙），下面我們來討論區(qū)間操作的splay。

splay的區(qū)間操作對比線段樹/數(shù)狀數(shù)組，支持：

• 區(qū)間刪除
• 區(qū)間翻轉(zhuǎn)

區(qū)間splay重要的操作是選擇區(qū)間，比如要對區(qū)間[l,r]進(jìn)行操作，我們要做的是將節(jié)點(diǎn)　l-1　Splay到根，再講節(jié)點(diǎn) r-1 splay到根節(jié)點(diǎn)的右兒子，那么根節(jié)點(diǎn)的右兒子的左子樹就是區(qū)間[l, r]?。ǜ鶕?jù)　左子樹的值<根節(jié)點(diǎn)的值<右子樹的值　的性質(zhì)）

其它區(qū)間求和，區(qū)間最小值，區(qū)間修改之類的類似與線段樹，通過lazy標(biāo)記來實現(xiàn)

我們來看一下這題

Tyvj1729 文藝平衡樹

您需要寫一種數(shù)據(jù)結(jié)構(gòu)（可參考題目標(biāo)題），來維護(hù)一個有序數(shù)列，其中需要提供以下操作：翻轉(zhuǎn)一個區(qū)間，例如原有序序列是5 4 3 2 1，翻轉(zhuǎn)區(qū)間是[2,4]的話，結(jié)果是5 2 3 4 1

需要注意的是，在上一題中，我們節(jié)點(diǎn)的權(quán)值是數(shù)的大小，在這一題中，我們的節(jié)點(diǎn)的權(quán)值是數(shù)的位置。

#include <bits/stdc++.h>
#define rep(i, a, b) for (int i=a; i<=b; i++)
#define drep(i, a, b) for (int i=b; i>=a; i--)
typedef long long LL;
using namespace std;

template <typename T>
struct Splay {
    struct node{
        node *ch[2], *parent, **root;
        T value;
        int size;
        bool bound, reverse;
        node(node *parent, node **root, const T &value, bool bound=false, bool reverse=false):parent(parent), root(root), value(value), reverse(false), size(1), bound(bound){
            ch[0]=ch[1]=NULL;
        }
        ~node(){
            if (ch[0]) delete(ch[0]);
            if (ch[1]) delete(ch[1]);
        }
        inline int relation(){return this==parent->ch[0]?0:1;}
        inline int lsize(){return ch[0] ? ch[0]->size : 0;}
        inline int rsize(){return ch[1] ? ch[1]->size : 0;}
        inline void maintain(){size = lsize() + rsize() +1;}
        inline node *grandparent(){return !parent ? NULL : parent->parent;}
        void *pushdown(){
            if (reverse){
                //swap(ch[0], ch[1]);
                node *tmp=ch[0];
                ch[0]=ch[1];
                ch[1]=tmp;
                if (ch[0]) ch[0]->reverse^=1;
                if (ch[1]) ch[1]->reverse^=1;
                reverse = false;
            }
        }
        void rotate(){
            parent->pushdown(), pushdown();
            node *old=parent;
            int x=relation();
            if (grandparent()) grandparent()->ch[old->relation()] = this;
            parent=grandparent();
            old->ch[x] = ch[x^1];
            if (ch[x^1]) ch[x^1]->parent = old;
            ch[x^1]=old;
            old->parent=this;
            old->maintain(), maintain();
            if (!parent) *root=this;
        }
        node *splay(node **target=NULL){
            if (!target) target=root;
            while (this!=*target){
                parent->pushdown();
                if (parent == *target) rotate();
                else if (parent->relation() == relation()) parent->rotate(), rotate();
                else rotate(), rotate();
            }
            return *target;
        }
    }*root;
    ~Splay() {
        if (root) delete root;
    }
    void build(const T *a, int n){
        root = build(a, 1, n, NULL);
        rep(i, 0, 1){
            node *bound_parent=NULL, **bound=&root;
            while (*bound){
                bound_parent = *bound;
                bound_parent->size++;
                bound = &(*bound)->ch[i];
            }
            *bound=new node(bound_parent, &root, 0, true);
        }
    }//插入邊界值
    node *build (const T *a, int l, int r, node *parent){
        if (l>r) return NULL;
        int mid=(l+r)>>1;
        node *v=new node(parent, &root, a[mid-1]);
        v->ch[0] = build(a, l, mid - 1, v);
        v->ch[1] = build(a, mid + 1, r, v);
        v->maintain();
        return v;
    }
    node *select(int k) {
        k++;
        node *v = root;
        while (v->pushdown(), k != v->lsize() + 1)
            if (k < v->lsize() + 1) v = v->ch[0]; else k -= v->lsize() + 1, v = v->ch[1];
        return v->splay();
    }
    node *&select(int l, int r) {
        node *lbound=select(l-1), *rbound=select(r+1);
        lbound->splay();
        rbound->splay(&lbound->ch[1]);
        return rbound->ch[0];
    }
    void reverse(int l, int r) {
        node *range = select(l, r);
        range->reverse ^= 1;
    }
    void fetch(T *a) {
        dfs(a, root);
    }
    void dfs(T *&a, node *v) {
        if (v) {
            v->pushdown();
            dfs(a, v->ch[0]);
            if (!v->bound) *a++=v->value;
            dfs(a, v->ch[1]);
        }
    }
};
Splay<int>splay;
const int MAXN=101000;
int n, m;
int a[MAXN];
int main() {
    scanf("%d%d", &n, &m);
    for (int i=0; i<n; i++) a[i]=i+1;
    splay.build(a, n);

    for (int i=0; i<m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        splay.reverse(l, r);
    }
    splay.fetch(a);
    for (int i=0; i<n; i++) printf("%d ", a[i]);
    return 0;
}