标签 - Trie树

树套树 工业 替罪羊树 Trie树    2017-01-06 12:43:39    292    1    0

3065: 带插入区间K小值

Time Limit: 60 Sec  Memory Limit: 512 MB
Submit: 2857  Solved: 881
[Submit][Status][Discuss]

Description

从前有n只跳蚤排成一行做早操,每只跳蚤都有自己的一个弹跳力a[i]。跳蚤国王看着这些跳蚤国欣欣向荣的情景,感到非常高兴。这时跳蚤国王决定理性愉悦一下,查询区间k小值。他每次向它的随从伏特提出这样的问题: 从左往右第x个到第y个跳蚤中,a[i]第k小的值是多少。
这可难不倒伏特,他在脑袋里使用函数式线段树前缀和的方法水掉了跳蚤国王的询问。
这时伏特发现有些跳蚤跳久了弹跳力会有变化,有的会增大,有的会减少。
这可难不倒伏特,他在脑袋里使用树状数组套线段树的方法水掉了跳蚤国王的询问。(orz 主席树)
这时伏特发现有些迟到的跳蚤会插入到这一行的某个位置上,他感到非常生气,因为……他不会做了。
请你帮一帮伏特吧。
快捷版题意:带插入、修改的区间k小值在线查询。

 

Input

第一行一个正整数n,表示原来有n只跳蚤排成一行做早操。
第二行有n个用空格隔开的非负整数,从左至右代表每只跳蚤的弹跳力。
第三行一个正整数q,表示下面有多少个操作。
下面一共q行,一共三种操作对原序列的操作:(假设此时一共m只跳蚤)
1. Q x y k: 询问从左至右第x只跳蚤到从左至右第y只跳蚤中,弹跳力第k小的跳蚤的弹跳力是多少。
    (1 <= x <= y <= m, 1 <= k <= y - x + 1)
2. M x val: 将从左至右第x只跳蚤的弹跳力改为val。
    (1 <= x <= m)
3. I x val: 在从左至右第x只跳蚤的前面插入一只弹跳力为val的跳蚤。即插入后从左至右第x只跳蚤是我刚插入的跳蚤。
    (1 <= x <= m + 1)

为了体现在线操作,设lastAns为上一次查询的时候程序输出的结果,如果之前没有查询过,则lastAns = 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^lastA