#P4278. 带插入区间K小值

带插入区间K小值

题目背景

本题时限已经修改为 2s

请使用常数较小的写法或者比较好的科技去过本题

题目描述

从前有nn只跳蚤排成一行做早操,每只跳蚤都有自己的一个弹跳力aia_i。跳蚤国王看着这些跳蚤国欣欣向荣的情景,感到非常高兴。这时跳蚤国王决定理性愉悦一下,查询区间kk小值。他每次向它的随从伏特提出这样的问题: 从左往右第xx个到第yy个跳蚤中,aia_ikk小的值是多少。

这可难不倒伏特,他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。

这时伏特发现有些跳蚤跳久了弹跳力会有变化,有的会增大,有的会减少。

这可难不倒伏特,他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。(orz 主席树)

这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上,他感到非常生气,因为……他不会做了。

请你帮一帮伏特吧。

快捷版题意:带插入、修改的区间k小值在线查询

输入格式

第一行一个正整数nn,表示原来有nn只跳蚤排成一行做早操。
第二行有nn个用空格隔开的非负整数,从左至右代表每只跳蚤的弹跳力。
第三行一个正整数qq,表示下面有多少个操作。
下面一共qq行,一共三种操作对原序列的操作:(假设此时一共mm只跳蚤)

  1. Q x y k: 询问从左至右第xx只跳蚤到从左至右第yy只跳蚤中,弹跳力第kk小的跳蚤的弹跳力是多少。(1xym,1kyx+11 \le x \le y \le m, 1 \le k \le y - x + 1)
  2. M x val: 将从左至右第x只跳蚤的弹跳力改为valval。(1xm1 \le x \le m)
  3. I x val: 在从左至右第xx只跳蚤的前面插入一只弹跳力为valval的跳蚤。即插入后从左至右第xx只跳蚤是我刚插入的跳蚤。(1xm+11 \le x \le m + 1)

为了体现在线操作,设lastAnslastAns为上一次查询的时候程序输出的结果,如果之前没有查询过,则lastAns=0lastAns = 0

则输入的时候实际是:

  • Q _x _y _k ——> 表示 Q _x^lastAns _y^lastAns _k^lastAns
  • M _x _val ——> 表示 M _x^lastAns _val^lastAns
  • I _x _val ——> 表示 I _x^lastAns _val^lastAns

简单来说就是操作中输入的整数都要异或上一次询问的结果进行解码。

(祝Pascal的同学早日转C++,就不提供pascal版的描述了。)

输出格式

对于每个询问输出回答,每行一个回答。

10
10 5 8 28 0 19 2 31 1 22
30
I 6 9
M 1 11
I 8 17
M 1 31
M 6 26
Q 2 7 6
I 23 30
M 31 7
I 22 27
M 26 18
Q 26 17 31
I 5 2
I 18 13
Q 3 3 3
I 27 19
Q 23 23 30
Q 5 13 5
I 3 0
M 15 27
Q 0 28 13
Q 3 29 11
M 2 8
Q 12 5 7
I 30 19
M 11 19
Q 17 8 29
M 29 4
Q 3 0 12
I 7 18
M 29 27
28
2
31
0
14
15
14
27
15
14

提示

n35000n \le 35000
插入个数 35000\le 35000,修改个数 70000\le 70000,查询个数 70000\le 70000 ,00 \le 每时每刻的权值 70000\le 70000

数据无梯度。