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

Splay解决区间问题[单点更新,区间最值询问]

 
阅读更多
/*http://acm.hdu.edu.cn/showproblem.php?pid=1754*/
/*单点更新,区间询问 splay实现*/
/*注意写rotateTo的时候。。*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 222222;
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],mx[MAXN],val[MAXN],a[MAXN];
    int root,tot;
    void init(){
        memset(ch,0,sizeof(int)*MAXN*2);
        memset(pre,0,sizeof(int)*MAXN);
        memset(sz,0,sizeof(int)*MAXN);
        memset(mx,-1,sizeof(int)*MAXN);
        root = tot = 0;
    }
    void read(int n){
        a[1] = a[n+2] = -1;
        for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
    }
    void push_up(int rt){
        mx[rt] = max(max(mx[l(rt)],mx[r(rt)]),val[rt]);
        sz[rt] = sz[l(rt)]+sz[r(rt)]+1;
    }
    void rotate(int x,int f){
        int y = pre[x];
        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 x,int goal){
        int k = root;
        while(1){
            if(x<(sz[l(k)]+1)) k = l(k);
            else if(x==(sz[l(k)]+1)){
                break;
            }else{
                x -= (sz[l(k)]+1);
                k = r(k);
            }
        }
        splay(k,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);
    }
    int query(int l,int r){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        return mx[l(r(root))];
    }
    void update(int pos,int c){
        rotateTo(pos,0);
        val[root] = c;
        push_up(root);
    }
    void debug(){
        printf("root:%d l(root):%d r(root):%d\n",root,l(root),r(root));
        dfs(root);
    }
    void dfs(int rt){
        if(!rt)return;
        dfs(l(rt));
        printf("node:%d max:%d size:%d val:%d lson:%d rson:%d pre:%d\n",rt,mx[rt],sz[rt],val[rt],l(rt),r(rt),pre[rt]);
        dfs(r(rt));
    }
};
SplayTree spt;
int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
        spt.init();
        spt.read(n);
        spt.buildTree(1,n+2,spt.root,0);
        char op[2]; int a,b;
        while(m--){
            scanf("%s%d%d",op,&a,&b);
            //spt.debug(); system("pause");
            if(op[0]=='Q'){
                printf("%d\n",spt.query(a+1,b+1));
            }else{
                spt.update(a+1,b);
            }
        }
    }
    return 0;
}

分享到:
评论
发表评论

文章已被作者锁定,不允许评论。

相关推荐

    Splay树题解1

    总的来说,Splay树是一种强大且灵活的数据结构,适用于解决需要高效动态维护区间信息的问题。其核心在于通过旋转操作优化访问路径,适应频繁访问的节点,使得操作时间复杂度在平均情况下得到改善。

    splay和动态树入门必看

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

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

    ### Splay Trees (伸展树) 教学知识点解析 #### 一、Splay Trees 概述 ...通过对Splay Trees的理解和运用,可以有效地解决多种计算机科学中的问题,特别是那些涉及到频繁数据访问和更新的应用场景。

    线段树总结

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

    线段树专辑

    例如,题目"敌兵布阵"和"I Hate It"展示了如何使用线段树实现单点更新和区间查询。在"敌兵布阵"中,线段树用于维护区间求和,而"I Hate It"则演示了如何使用线段树找到区间内的最值。 线段树的灵活性和高效性使其...

    线段树.pdf

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

    平衡树Splay代码

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

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

    给定一个长度为N的序列,每个序列的长度是一个整数。... 将[L,R]这个区间所有数加上V.  将[L,R]这个区间翻转,例如 1234变成 4321  求[L,R]区间的最大值 能力有限,实现可能有纰漏,也没有用到lazy_tag

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

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

    SplayTree详细解释

    - **操作复杂度**:虽然单次操作的时间复杂度为O(h),但由于SplayTree具有良好的摊还性能分析,其平均操作时间复杂度可以达到O(log N)。 #### 伸展操作(Splay) 伸展操作Splay(x, S)是指在保持伸展树有序性的前提...

    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伸展树结构体模板

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

    完全版线段树

    `update(int p, int add, int l, int r, int rt)`函数执行单点更新,根据位置`p`和增量`add`更新区间[l, r]。`query(int L, int R, int l, int r, int rt)`函数则用于区间查询,返回[L, R]区间的值。 以下是代码...

    Splay(C++)示例代码

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

    splay 伸展树.ppt

    splay 伸展树.ppt

Global site tag (gtag.js) - Google Analytics