`
Coco_young
  • 浏览: 125321 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

Splay解决区间问题[区间切割,区间翻转]

 
阅读更多

区间翻转:由于以root为根的树的中序遍历表示该区间,那么翻转只要递归的交换左右子树即可,加入lazy思想,降低时间复杂度。

Tips:做区间翻转的时候rev[rt]的含义是——以rt为根的子树所表示的区间是否将要被翻转,目前并没有执行翻转操作,如果改成先翻转,再标记,就会出现大问题。

Code:没用的push_down写多了。

/*http://acm.hdu.edu.cn/showproblem.php?pid=3487*/
/*splay区间切割+翻转*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 333333;
#define m_set(ptr,v,type,size) memset(ptr,v,sizeof(type)*size)
#define loop(begin,end) for(int i=begin;i<end;i++)
class SplayTree{
    #define l(x) (ch[x][0])
    #define r(x) (ch[x][1])
    #define mid(x,y) ((x+y)>>1)
public:
    int ch[MAXN][2],pre[MAXN];
    int sz[MAXN],val[MAXN],rev[MAXN],a[MAXN];
    int root,tot;
    void init(){
        m_set(ch,0,int,MAXN*2);
        m_set(pre,0,int,MAXN);
        m_set(sz,0,int,MAXN);
        m_set(val,0,int,MAXN);
        m_set(rev,0,int,MAXN);
        root = tot = 0;
    }
    void read(int n){
        a[1] = a[n+2] = 0;
        loop(2,n+2){ a[i] = i-1; }
    }
    void push_up(int rt){
        sz[rt] = sz[l(rt)]+sz[r(rt)]+1;
    }
    void swap(int &x,int &y){
        int tmp = x;
        x = y;
        y = tmp;
    }
    void push_down(int rt){
        if(rt&&rev[rt]){
            swap(l(rt),r(rt));
            if(l(rt)) rev[l(rt)] ^= 1;
            if(r(rt)) rev[r(rt)] ^= 1;
            rev[rt] = 0;
        }
    }
    void rotate(int x,int f){
        int y = pre[x];
        push_down(x);
        push_down(y);
        ch[y][!f] = ch[x][f];
        if(ch[y][!f]) pre[ch[y][!f]] = y;
        push_up(y);
        if(pre[y]) ch[pre[y]][r(pre[y])==y] = x;
        pre[x] = pre[y];
        ch[x][f] = y;
        pre[y] = x;
    }
    void splay(int x,int goal){
        push_down(x);
        while(pre[x]!=goal){
            int y = pre[x], z = pre[pre[x]];
            if(z==goal){
                rotate(x,l(y)==x);
            }else{
                int f = l(z)==y;
                if(ch[y][!f]==x){
                    rotate(y,f); rotate(x,f);
                }else{
                    rotate(x,!f); rotate(x,f);
                }
            }
        }
        push_up(x);
        if(goal==0) root = x;
    }
    void rotateTo(int k,int goal){
        int x = root;
        while(1){
            push_down(x);
            int tmp = sz[l(x)]+1;
            if(k==tmp) break;
            else if(k<tmp) x = l(x);
            else{
                k -= tmp;
                x = r(x);
            }
        }
        splay(x,goal);
    }
    void buildTree(int l,int r,int &rt,int f){
        if(l>r)return;
        int m = mid(l,r);
        rt = ++tot;
        val[rt] = a[m];
        pre[rt] = f;
        buildTree(l,m-1,l(rt),rt);
        buildTree(m+1,r,r(rt),rt);
        push_up(rt);
    }
    void rangeCut(int l,int r,int goal){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        push_down(r(root));
        int x = l(r(root));
        l(r(root)) = 0;
        pre[x] = 0;
        push_up(r(root));
        push_up(root);
        rotateTo(goal,0);
        rotateTo(goal+1,root);
        push_down(r(root));
        l(r(root)) = x;
        pre[x] = r(root);
        push_up(r(root));
        push_up(root);
    }
    void rangeFlip(int l,int r){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        push_down(r(root));
        int x = l(r(root));
        rev[x] ^= 1;
    }
    void dfs(int rt,int &size){
        if(!rt) return;
        push_down(rt);
        dfs(l(rt),size);
        a[size++] = val[rt];
        dfs(r(rt),size);
    }
    /////////////////debug///////////////////////

}spt;
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m),!(n<0&&m<0)){
        spt.init();
        spt.read(n);
        spt.buildTree(1,n+2,spt.root,0);
        char op[5]; int a,b,c;
        while(m--){
            scanf("%s%d%d",op,&a,&b);
            if(op[0]=='C'){
                scanf("%d",&c);
                spt.rangeCut(a+1,b+1,c+1);
            }else{
                spt.rangeFlip(a+1,b+1);
            }
        }
        n = 0;
        spt.dfs(spt.root,n);
        loop(1,n-1){
            if(i!=1)printf(" ");
            printf("%d",spt.a[i]);
        }
        printf("\n");
    }
    return 0;
}

 

分享到:
评论

相关推荐

    Splay树题解1

    2. 区间翻转操作:这个操作相对简单,只需在节点上添加一个翻转标记,表示该区间内的元素顺序需要翻转。在实际应用中,可能需要对节点进行特殊处理,以便在后续查询时正确反映区间内的元素顺序。 3. 区间插入操作:...

    splay和动态树入门必看

    在ACM/ICPC和IOI等竞赛中,Splay树常用于解决诸如区间查询、区间更新、最近点对等问题。例如,在处理区间查询时,可以使用Splay树快速定位区间边界,同时进行必要的旋转以优化树的结构。在区间更新问题中,Splay树...

    伸展树的基本实现和区间操作

    给定一个长度为N的序列,每个序列的长度是一个整数。要支持以下三种操作: ... 将[L,R]这个区间翻转,例如 1234变成 4321  求[L,R]区间的最大值 能力有限,实现可能有纰漏,也没有用到lazy_tag

    Splay.pdf【算法与数据结构】

    - **解决思路**:在Splay Trees的基础上增加翻转操作的功能,利用标记记录翻转状态,通过旋转操作传播翻转标记。 ##### 示例2:多项式操作 - **问题描述**:给定一个多项式`a0*x^0 + a1*x^1 + ... + an*x^n`,进行`...

    平衡树Splay代码

    Splay,平衡树的一种,支持部分区间操作。

    Splay伸展树结构体模板

    Splay结构体的模板,含有各种旋转、插入、翻转等操作,注释清晰

    splay 模板

    splay经典代码,hdu1890,经典入门题,可作为模板

    Splay(伸展树)模板

    Splay模板包括旋转,主函数Splay,插入,删除,最大值,最小值,查询k大,查询排名

    Splay说明论文

    讲解Splay的经典论文 -------- Randomized Splay Trees: Theoretical and Experimental Results Susanne Albers Marek Karpinski

    splaytree.zip

    展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。

    Splay(C++)示例代码

    伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...

    splay 伸展树.ppt

    splay 伸展树.ppt

    splay平衡树

    splay程序,希望大家可以看一下,适合新手

    运用伸展树解决数列维护问题 by Crash

    使用伸展树可以有效地解决这类问题,尽管伸展树在区间修改和查询方面比线段树稍显复杂,但它在某些特殊情况下,如需要频繁地访问并修改最近访问过的节点时,能够展现出更高的效率。 最后,文章中还比较了伸展树与...

    splay tree C# code 伸展树的C#代码实现

    伸展树(Splay Tree)是一种自调整的二叉搜索树数据结构,它通过操作将最近访问的元素移动到树的根部,从而优化查找、插入和删除等操作的平均性能。C#语言中的伸展树实现涉及了对二叉树节点的操作、旋转算法以及对树...

    Splay Tree

    伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 ...

    线段树总结

    提供的代码示例展示了如何使用线段树解决单点更新和区间查询的问题。例如,`ohdu1166 敌兵布阵` 这道题目中,线段树的功能是更新单点并查询区间和。`build` 函数用于构建线段树,`update` 函数用于更新,`query` ...

Global site tag (gtag.js) - Google Analytics