#P3217. ALOEXT

ALOEXT

ALOEXT

题目描述

taorunz 在密室里发现一排存有 OI 资料的可移动存储器。每个存储器上写有一个非负整数。选定区间 [l,r][l,r](l<rl<r)后,他可以从第 ll 个到第 rr 个之间任选一个存储器,包含区间两端。获得的知识量等于该存储器上写的数字与区间数字的次大值的按位异或结果。次大值指按从大到小排序后的第二个值,相同数字分别计数。

存储器可能插入、消失或更改数字。对于 taorunz 指定的每个区间,求能获得的最大知识量。查询本身不会改变这一排存储器。

输入格式

第一行包含两个整数 N,MN,M(1≤N,M≤1051\le N,M\le 10^5),分别表示初始存储器数和事件数。

第二行包含 NN 个非负整数,按从左到右的顺序给出初始数字。存储器下标从 00 开始。

接下来 MM 行,每行描述一个事件。以下参数表示解密后的值:

事件 含义
I x y 在原第 xx 个存储器前插入一个数字为 yy 的存储器。按插入位置定义,xx 等于原存储器数时表示插到末尾。
D x 删除第 xx 个存储器。
C x y 把第 xx 个存储器上的数字改为 yy。
F l r 查询区间 [l,r][l,r] 可获得的最大知识量。保证解密后 l<rl<r。

本题强制在线。设 n0n_0 为该事件发生前当前的存储器数,last_ans\mathrm{last\_ans} 为最近一次 F 查询的答案,首次查询前为 00。事件中读到一个整数 ss 时,按参数类型解密:

  • I、D、C 的位置 xx 和 F 的两端 l,rl,r 的真实值是 (s+last_ans) mod n0(s+\mathrm{last\_ans})\bmod n_0。
  • I、C 的数值 yy 的真实值是 (s+last_ans) mod 1048576(s+\mathrm{last\_ans})\bmod 1048576。

按输入的解密规则,插入位置落在 00 到 n0−1n_0-1 之间。

输出格式

按顺序对每个 F 事件输出一行一个整数,表示查询结果。

5 10
2 6 3 8 7
F 1 4
I 2 1048565
I 0 1048566
D 3
F 3 0
I 3 1048569
D 5
C 1 1048570
F 1 2
F 2 1
15
7
4
7

原题共有五组数据,其中一组为随机数据,其余为人工构造。

原题面 PDF

注意:数值模 10485761048576 的规则只用于 I、C 事件的新数值解码,不会截断初始数字。