P5055 【模板】可持久化文艺平衡树

    • 240通过
    • 766提交
  • 题目提供者 小粉兔
  • 评测方式 云端评测
  • 标签 Treap 可持久化 平衡树 替罪羊树
  • 难度 NOI/NOI+/CTSC
  • 时空限制 2500ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    这是一道模板题。

    题目描述

    您需要写一种数据结构,来维护一个序列,其中需要提供以下操作(对于各个以往的历史版本):

    1. 在第 $p$ 个数后插入数 $x$ 。
    2. 删除第 $p$ 个数。
    3. 翻转区间 $[l,r]$,例如原序列是 $\{5,4,3,2,1\}$,翻转区间 $[2,4]$ 后,结果是 $\{5,2,3,4,1\}$。
    4. 查询区间 $[l,r]$ 中所有数的和。

    和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本(操作 $4$ 即保持原版本无变化),新版本即编号为此次操作的序号。

    本题强制在线。

    输入输出格式

    输入格式:

    第一行包含一个正整数 $N$,表示操作的总数。

    接下来 $N$ 行,每行前两个整数 $v_i,opt_i$,$v_i$ 表示基于的过去版本号 $(0\le v_i<i)$,$opt_i$ 表示操作的序号 $(1\le opt_i\le 4)$。

    若 $opt_i=1$,则接下来两个整数 $p_i,x_i$,表示操作为在第 $p_i$ 个数后插入数 $x$ 。
    若 $opt_i=2$,则接下来一个整数 $p_i$,表示操作为删除第 $p_i$ 个数。
    若 $opt_i=3$,则接下来两个整数 $l_i,r_i$,表示操作为翻转区间 $[l_i,r_i]$。
    若 $opt_i=4$,则接下来两个整数 $l_i,r_i$,表示操作为查询区间 $[l_i,r_i]$ 的和。

    强制在线规则:
    令当前操作之前的最后一次 $4$ 操作的答案为 $lastans$(如果之前没有 $4$ 操作,则 $lastans=0$)。
    则此次操作的 $p_i,x_i$ 或 $l_i,r_i$ 均按位异或上 $lastans$ 即可得到真实的 $p_i,x_i$ 或 $l_i,r_i$。

    输出格式:

    对于每个序号为 $4$ 的查询操作,输出一行一个数表示区间的和。

    输入输出样例

    输入样例#1: 复制
    10
    0 1 0 1
    1 1 1 2
    2 4 1 2
    3 1 2 0
    4 4 2 1
    5 3 5 7
    6 4 5 6
    4 1 7 1
    8 3 4 6
    9 4 4 1
    输出样例#1: 复制
    3
    4
    5
    10

    说明

    强制在线:以下针对 $p_i,x_i,l_i,r_i$ 的限制均是按位异或 $lastans$ 后的限制。

    对于 $30\%$ 的数据,$N\le 5000$。

    对于另外 $30\%$ 的数据,$v_i=i-1$。

    对于 $100\%$ 的数据,$1\le N\le 2\times 10^5$,$-10^6<x_i<10^6$。

    假设基于的历史版本的序列长度为 $len\ge 1$,有:
    若 $opt_i=1$,则 $0\le p_i\le len$。
    若 $opt_i=2$,则 $1\le p_i\le len$。
    若 $opt_i=3$,则 $1\le l_i\le r_i\le len$。
    若 $opt_i=4$,则 $1\le l_i\le r_i\le len$。

    假设基于的历史版本的序列长度为 $0$,有:
    $opt_i=1$,$p_i=0$。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。