splay学习笔记(上）

前不久其实已经学过splay了，但是总觉得似乎不能灵活地改造它，于是重新学习了一波。

感谢https://oi.men.ci/splay-notes-1/
关于splay的解释这里说的也比较清楚
下面我们分成单点版和区间版讨论

入门题 Tyvj 1728 普通平衡树

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

#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;
        }//前驱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的原理其实没有太大关系，这个板子已经把splay的基本操作封装再node结构体里面了，可以理解成splay是一个一直在维护平衡的名次树。所以起码要理解名次树的性质：

左子树的值<根节点的值<右子树的值

上面的splay只支持单点操作，其实用线段树也可以实现（强烈推荐zkw的论文《统计的力量》，很精妙），下面我们来讨论区间操作的splay。

splay的区间操作对比线段树/数状数组，支持：

  • 区间删除
  • 区间翻转

区间splay重要的操作是选择区间，比如要对区间[l,r]进行操作，我们要做的是将节点　l-1　Splay到根，再讲节点 r-1 splay到根节点的右儿子，那么根节点的右儿子的左子树就是区间[l, r]　（根据　左子树的值<根节点的值<右子树的值　的性质）

其它区间求和，区间最小值，区间修改之类的类似与线段树，通过lazy标记来实现

我们来看一下这题

Tyvj1729 文艺平衡树

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

需要注意的是，在上一题中，我们节点的权值是数的大小，在这一题中，我们的节点的权值是数的位置。

#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;
}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,837评论 6赞 496
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,551评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,417评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,448评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,524评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,554评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,569评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,316评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,766评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,077评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,240评论 1赞 343
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,912评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,560评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,176评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,425评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,114评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,114评论 2赞 352

推荐阅读更多精彩内容

  • 面试高级算法梳理笔记
    归去来兮。 1.1 说明 本篇为《挑战程序设计竞赛（第2版）》[http://www.ituring.com.cn...
    尤汐Yogy阅读 14,321评论 0赞 160
  • 风雨无阻战友情，无私奉献显大爱
    2018年8月10日，牛商会海豹战队队友们从百忙中抽出宝贵的时间冒雨莅临和胜帮扶，而且请到了细分领域营销高手——雄...
    宋_宋阅读 739评论 0赞 0
  • 我的生活
    我一个30多岁的女人。有个爱我的老公。有两个可爱的儿子。有份收入不高但挺自由的工作。 我觉得自己是一个做任...
    爱上红麦子阅读 189评论 0赞 0