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

Splay解决区间问题[区间更新,区间求和]

 
阅读更多
/*http://poj.org/problem?id=3468*/
/*区间更新,区间求和*/
/*注意各种编码细节,特别是splay buildTree和 rotateTo*/
/*仔细体会与线段树解决区间问题的不同点,如结点记录的信息是不同的*/
/*lazy思想*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 111111;
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],sz[MAXN];
    long long sum[MAXN],add[MAXN],val[MAXN];
    int a[MAXN];
    int tot,root;
    void init(){
        memset(ch,0,sizeof(int)*MAXN*2);
        memset(pre,0,sizeof(int)*MAXN);
        memset(sz,0,sizeof(int)*MAXN);
        memset(sum,0,sizeof(long long)*MAXN);
        memset(add,0,sizeof(long long)*MAXN);
        memset(val,0,sizeof(long long)*MAXN);
        tot = root = 0;
    }
    void read(int n){
        a[1] = a[n+2] = 0;
        for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
    }
    void push_up(int rt){
        sum[rt] = sum[l(rt)]+sum[r(rt)]+val[rt];
        sz[rt] = sz[l(rt)]+sz[r(rt)]+1;
    }
    void push_down(int rt){
        if(add[rt]){
            if(l(rt)){
                val[l(rt)] += add[rt];
                add[l(rt)] += add[rt];
                sum[l(rt)] += add[rt]*sz[l(rt)];
            }
            if(r(rt)){
                val[r(rt)] += add[rt];
                add[r(rt)] += add[rt];
                sum[r(rt)] += add[rt]*sz[r(rt)];
            }
            add[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){
        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);
            if(k==(sz[l(x)]+1)) break;
            else if(k<(sz[l(x)]+1)) x = l(x);
            else{
                k -= sz[l(x)]+1;
                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;
        pre[rt] = f;
        val[rt] = a[m];
        buildTree(l,m-1,l(rt),rt);
        buildTree(m+1,r,r(rt),rt);
        push_up(rt);
    }
    long long query(int l,int r){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        return sum[l(r(root))];
    }
    void update(int l,int r,int c){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        val[l(r(root))] += c;
        sum[l(r(root))] += c*sz[l(r(root))];
        add[l(r(root))] += c;
    }
}spt;
int main(){
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
        spt.init();
        spt.read(n);
        spt.buildTree(1,n+2,spt.root,0);
        char op[2]; int a,b,c;
        while(q--){
            scanf("%s%d%d",op,&a,&b);
            if(op[0]=='Q'){
                printf("%I64d\n",spt.query(a+1,b+1));
            }else{
                scanf("%d",&c);
                spt.update(a+1,b+1,c);
            }
        }
    }
    return 0;
}

分享到:
评论

相关推荐

    线段树.pdf

    它可以用于解决诸如区间求和、区间最值等区间查询问题,并支持单点更新和成段更新等操作。 首先,线段树的实现基础是二叉树结构。每个节点代表一个区间,树的叶子节点对应实际数据中的单个元素。非叶子节点可以看作...

    线段树专辑

    线段树的灵活性和高效性使其成为解决大量区间查询和更新问题的首选工具。随着对更高级数据结构如Splay树的学习,线段树的实现方式可以变得更优雅、简洁,进一步提升性能。在编写线段树的代码时,注意合理设置节点...

    完全版线段树

    - `ohdu1166 敌兵布阵`:这是一个基础的线段树题目,仅涉及单点更新和区间求和。 - `ohdu1754 I Hate It`:虽然题目描述未给出,但根据上下文,可以推测这同样是一个涉及到线段树的更新和查询的问题。 线段树的优化...

    IOI国家集训队论文集1999-2019

    姜尚仆 -《模线性方程的应用——用数论方法解决整数问题》 金 恺 -《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》 雷环中 -《结果提交类问题》 林希德 -《求最大重复子串》 刘才良 -《平面图在信息...

    高级数据结构c++

    线段树通常用于解决区间最值、区间加减等问题,对于动态维护区间信息的场景非常有用。 2. **Splay树**:Splay树是一种自调整二叉搜索树,其特点是每次访问节点时都会通过旋转操作(zig、zag、zig-zag、zig-zig)将...

    ACM程序设计竞赛模板完全版

    2. **莫队算法**:莫队算法是一种用于解决区间查询问题的组合算法,常用于解决区间求和、区间最大值、区间最小值等问题。 3. **数据结构**:在ACM模板中,数据结构部分广泛应用于快速检索、存储和修改数据,例如: ...

    acm-book.pdf

    线段树是一种能够高效处理区间查询和更新操作的数据结构,常用于解决区间最大/最小值、区间求和等问题。 #### 4.4 字典树 字典树是一种树形结构,用于存储大量的字符串,支持高效的查找、插入和删除操作。在文本...

    信息学奥赛-省选及NOI课程表(2020.08.31).pdf

    4. **线段树**:用于高效地进行区间查询和更新操作的数据结构,通常应用于区间求和或最值等问题。 5. **可持久化数据结构**:在每次修改数据结构时都会保留其修改前的状态,方便进行历史版本的查询。 6. **树套树**...

    acm-icpc模板

    树状数组是一种支持在一维数组上进行单点更新和区间求和操作的数据结构,具有较高的效率。 ##### 线段树 线段树是一种支持在数组上进行区间修改和区间查询操作的数据结构,广泛应用于区间问题中。 ##### 字典树 ...

    ACMer 要学的知识

    8. **树状数组**:又称区间更新、单点查询的数据结构,适用于求区间和等问题。 9. **赫夫曼树与赫夫曼编码**:用于数据压缩的树结构,赫夫曼编码是构建树过程中形成的编码。 **五、字符串匹配** 1. **Trie树**:又...

    九野的模版3.15.10.pdf

    - **树状数组**:也称为二叉索引树,用于高效地实现单点更新和区间求和操作。 - **RMQ (Range Minimum Query)**:区间最小值查询,常使用树状数组或线段树解决。 - **树链剖分**:将树分解成若干个重链和轻节点,以...

Global site tag (gtag.js) - Google Analytics