TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3269
  • 题目
  • P3269可持久化平衡树
    限制 : 时间限制 : 10000 MS   空间限制 : 565536 KB
    问题描述

    有一个序列,初始状态有n个数,m次操作,有以下几种操作:
    1.在第x个数后面插入一个值为t的数;
    2.把第x个数删掉;
    3.查询第l个数到第r个数的最大值;
    4.回到第k个操作后的状态(如果k=0表示回到初始状态)。
    为了防止用离线做法水过,当然就要强制在线。
    设当前序列有N个数,当前是第M次操作,上次答案是lastans,一开始lastans=0,加密规则如下:
    1.输入xx,tt,则x=(xx+lastans)%(N+1),t=tt^lastans。
    2.输入xx,则x=(xx+lastans)%N+1。
    3.输入ll,rr,则l=(ll+lastans)%N+1,r=(rr+lastans*2)%N+1,如果l>r就交换一下。
    4.输入kk,则k=(kk+lastans)%M。

    输入格式

    第一行两个整数n,m,表示序列的初始长度和操作数。
    第二行n个数,表示初始序列。
    接下来m行每行第一个数是操作的编号,后面的若干个数表示这次操作的内容。

    输出格式

    每次查询输出答案。

    样例输入

    5 5
    1 2 3 4 5 
    1 2 3
    2 3
    3 4 5
    4 3
    3 2 1

    样例输出

    5
    3

    提示

    1<=n,m<=200000
    所有输入都是非负整数且不超过229-1。


    来源  感谢nodgd