【xsy1629】可持久化序列 - 可持久化平衡树

时间:2022-12-20 17:14:38

题意

你现在要用数据结构维护一个长度为n的序列。

这个序列支持三种操作:

1 l r:将序列中的第l项到第r项这一段翻转。

2 l r:查询序列中[l,r]这一段的和。

3 p:回到第p个历史版本。

每一个翻转操作的时候记作序列处于一次新的版本,初始的版本是0。

每一个回到历史版本之后再操作的版本都是一个最新版本,不是第p+1版本。

\(1\leq n\leq 50000\)

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

#define rep(i,a,b) for (int i=(a);i<=(b);i++)

const int N=65536;
const int M=65536;
const int S=8388608;

int n,m;
int a[N];

namespace Treap {
    int rt[M],nowVer,allVer;
    int tot;
    struct Node {
        int c[2]; int rev;
        int fix;    //fix=dep
        int dat,sum;
        int siz;
        Node(int _fix=0,int _dat=0,int _siz=0) {
            c[0]=c[1]=rev=0;
            fix=_fix;
            dat=sum=_dat;
            siz=_siz;
        }
    }tr[S];
    struct D {
        int c[2];
        D(void) {
            c[0]=c[1]=0;
        }
    };

    void Update(int x) {
        tr[x].sum=tr[tr[x].c[0]].sum+tr[tr[x].c[1]].sum+tr[x].dat;
        tr[x].siz=tr[tr[x].c[0]].siz+tr[tr[x].c[1]].siz+1;
    }

    int New_Node(int key,int fix,int dat) {
        int x=++tot;
        tr[x]=Node(fix,dat,1);
        return x;
    }

    int Copy_Node(int form) {
        int x=++tot;
        tr[x]=tr[form];
        return x;
    }

    int Build(int *a,int l,int r,int dep) {
        int mid=(l+r)>>1;
        int x=New_Node(mid,dep,a[mid]);
        if (l<mid)
            tr[x].c[0]=Build(a,l,mid-1,dep+1);
        if (mid<r)
            tr[x].c[1]=Build(a,mid+1,r,dep+1);
        Update(x);
        return x;
    }

    void Clear(int x) {
        if (!tr[x].rev) return; tr[x].rev=0;
        if (tr[x].c[0]>0) {
            tr[x].c[0]=Copy_Node(tr[x].c[0]);
            tr[tr[x].c[0]].rev^=1;
        }
        if (tr[x].c[1]>0) {
            tr[x].c[1]=Copy_Node(tr[x].c[1]);
            tr[tr[x].c[1]].rev^=1;
        }
        swap(tr[x].c[0],tr[x].c[1]);
    }

    D Split(int x,int rk) {
        D t; if (!x) return t;
        int x1=Copy_Node(x); Clear(x1);
        if (rk<=tr[tr[x1].c[0]].siz) {
            t=Split(tr[x1].c[0],rk);
            tr[x1].c[0]=t.c[1]; Update(x1);
            t.c[1]=x1;
        }
        else if (rk==tr[tr[x1].c[0]].siz+1) {
            t.c[1]=tr[x1].c[1];
            tr[x1].c[1]=0; Update(x1);
            t.c[0]=x1;
        }
        else {
            t=Split(tr[x1].c[1],rk-1-tr[tr[x1].c[0]].siz);
            tr[x1].c[1]=t.c[0]; Update(x1);
            t.c[0]=x1;
        }
        return t;
    }

    int Merge(int x1,int x2) {
        if (!x1) return x2;
        if (!x2) return x1;
        if (tr[x1].fix<tr[x2].fix) {
            int x3=Copy_Node(x1);
            Clear(x3);
            tr[x3].c[1]=Merge(tr[x3].c[1],x2);
            Update(x3);
            return x3;
        }
        else {
            int x3=Copy_Node(x2);
            Clear(x3);
            tr[x3].c[0]=Merge(x1,tr[x3].c[0]);
            Update(x3);
            return x3;
        }
    }
}

int rd(void) {
    int x=0,f=1; char c=getchar();
    while (!isdigit(c)) {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (isdigit(c)) {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}

void Goto(int p) {
    using namespace Treap;
    nowVer=p;
}

void Reverse(int l,int r) {
    using namespace Treap;
    D t1=Split(rt[nowVer],r);
    D t2=Split(t1.c[0],l-1);    //use t2.c[1]
    int x=Copy_Node(t2.c[1]);
    tr[x].rev^=1;
    rt[++allVer]=Merge(Merge(t2.c[0],x),t1.c[1]);
    nowVer=allVer;
}

int Query(int l,int r) {
    using namespace Treap;
    D t1=Split(rt[nowVer],r);
    D t2=Split(t1.c[0],l-1);
    return tr[t2.c[1]].sum;
}

int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("N.in","r",stdin);
        freopen("N.out","w",stdout);
    #endif

    n=rd(),m=rd();
    rep(i,1,n) a[i]=rd();
    Treap::rt[0]=Treap::Build(a,1,n,1);

    rep(i,1,m) {
        int c=rd();
        switch (c) {
            case 1: {
                int l=rd(),r=rd();
                Reverse(l,r);
                break;
            }
            case 2: {
                int l=rd(),r=rd();
                int ans=Query(l,r);
                printf("%d\n",ans);
                break;
            }
            case 3: {
                int p=rd();
                Goto(p);
                break;
            }
        }
    }

    return 0;
}

【xsy1629】可持久化序列 - 可持久化平衡树的更多相关文章

  1. 可持久化Trie &amp&semi; 可持久化平衡树 专题练习

    [xsy1629]可持久化序列 - 可持久化平衡树 http://www.cnblogs.com/Sdchr/p/6258827.html [bzoj4260]REBXOR - Trie 事实上只是一 ...

  2. luogu P3919 &lbrack;模板&rsqb;可持久化数组&lpar;可持久化线段树&sol;平衡树&rpar;&lpar;主席树&rpar;

    luogu P3919 [模板]可持久化数组(可持久化线段树/平衡树) 题目 #include<iostream> #include<cstdlib> #include< ...

  3. Redis的两种持久化方式-快照持久化和AOF持久化

    Redis为了内部数据的安全考虑,会把本身的数据以文件形式保存到硬盘中一份,在服务器重启之后会自动把硬盘的数据恢复到内存(redis)的里边,数据保存到硬盘的过程就称为"持久化"效 ...

  4. Redis的两种持久化方式-快照持久化(RDB)和AOF持久化

    Redis为了内部数据的安全考虑,会把本身的数据以文件形式保存到硬盘中一份,在服务器重启之后会自动把硬盘的数据恢复到内存(redis)的里边,数据保存到硬盘的过程就称为“持久化”效果. redis有两 ...

  5. Hibernate,Session方法使得java对象进入持久化状态;持久化对象特征

    以下情况java对象进入持久化状态: session.save()方法把临时对象转变为持久化对象. session.load()和session.get()方法得到的对象总是处于持久化状态. sess ...

  6. Redis数据持久化之AOF持久化

    一.RDB持久化的缺点创建RDB文件需要将服务器所有的数据库的数据都保存起来,这是一个非常耗费资源和时间的操作,所以服务器需要隔一段时间才能创建一个新的RDB文件,就也是说创建RDB文件的操作不能执行 ...

  7. JMS学习&lpar;五&rpar;--ActiveMQ中的消息的持久化和非持久化 以及 持久订阅者 和 非持久订阅者之间的区别与联系

    一,消息的持久化和非持久化 ①DeliveryMode 这是传输模式.ActiveMQ支持两种传输模式:持久传输和非持久传输(persistent and non-persistent deliver ...

  8. redis系列:RDB持久化与AOF持久化

    前言 什么是持久化? 持久化(Persistence),即把数据(如内存中的对象)保存到可永久保存的存储设备中(如磁盘).持久化的主要应用是将内存中的对象存储在数据库中,或者存储在磁盘文件中.XML数 ...

  9. RabbitMQ学习笔记(6)----RabbitMQ 持久化和非持久化

    持久化:将交换机或队列数据保存到磁盘,服务器宕机或重启之后依然存在. 非持久化:将交换机或队列的数据保存到内存中,服务器宕机或重启之后数据将不存在. 在RabbitMQ中也提供了持久化和非持久化方式. ...

随机推荐

  1. dispatch&lowbar;set&lowbar;target&lowbar;queue 说明

    参照:http://blog.csdn.net/growinggiant/article/details/41077221 http://codingobjc.com/blog/2013/05/07/ ...

  2. Spark之SQL解析(源码阅读十)

    如何能更好的运用与监控sparkSQL?或许我们改更深层次的了解它深层次的原理是什么.之前总结的已经写了传统数据库与Spark的sql解析之间的差别.那么我们下来直切主题~ 如今的Spark已经支持多 ...

  3. 【测试】手工搭建DG

    前言:(一)准备工作: 1.数据库要处于归档模式: 2.监听参数:local_listener 默认值为空--1521 3.关闭闪回(可能会触发数据库的bug,备库不能开闪回) 4.如果有外部表,外部 ...

  4. Oracle 课程八之性能优化之Oracle SQL Trace

    一. SQL_TRACE 当SQL语句出现性能问题时,我们可以用SQL_TRACE来跟踪SQL的执行情况,通过跟踪,我们可以了解一条SQL或者PL/SQL包的运行情况,SQL_TRACE命令会将SQL ...

  5. 【M15】了解异常处理(exception handling)的成本

    1.为了在运行期处理异常,程序必须做大量额外的工作.比如,即使抛出异常,也必须保证离开作用域的栈上对象执行析构方法.因此,必须记录try语句的进入点和离开点,记录catch语句能够处理的异常等.这就意 ...

  6. POJ 3652 &amp&semi;amp&semi; ZOJ 2934 &amp&semi;amp&semi; HDU 2721 Persistent Bits(数学 元)

    主题链接: PKU:http://poj.org/problem?id=3652 ZJU:http://acm.zju.edu.cn/onlinejudge/showProblem.do? probl ...

  7. 51 nod 1515 明辨是非&lpar;并查集合并&rpar;

    1515 明辨是非题目来源: 原创基准时间限制:1 秒 空间限制:131072 KB 分值: 160 难度:6级算法题 给n组操作,每组操作形式为x y p. 当p为1时,如果第x变量和第y个变量可以 ...

  8. mysq基础操作

    创建表: create table customer(mid char(5) primary key,name varchar(20),birth date,sex char(1) DEFAULT ' ...

  9. 转:2016年崛起的js项目

    近几年 JS 社区创新和演化的速度是有目共睹的,几个月前比较时髦的技术很可能现在已经过时了. 2016 已经过去,你有没有担心错过了什么重要的内容?在这篇调查报告中我们会为你解读社区的主流趋势. 我们 ...

  10. spring mvc入门配置

    现在主流的Web MVC框架除了Struts这个主力 外,其次就是Spring MVC了,因此这也是作为一名程序员需要掌握的主流框架,框架选择多了,应对多变的需求和业务时,可实行的方案自然就多了.不过 ...