标签 - 工业

树套树 工业 替罪羊树 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

线段树 工业 技巧    2016-12-06 20:03:57    357    0    0

妈妈我终于会写线段树了!

动态树分治 替罪羊树 treap 工业    2016-10-22 09:22:49    216    -7    2

#55. 【WC2014】紫荆花之恋

 统计

 

强强和萌萌是一对好朋友。有一天他们在外面闲逛,突然看到前方有一棵紫荆树。这已经是紫荆花飞舞的季节了,无数的花瓣以肉眼可见的速度从紫荆树上长了出来。

仔细看看的话,这个大树实际上是一个带权树。每个时刻它会长出一个新的叶子节点,每个节点上有一个可爱的小精灵,新长出的节点上也会同时