#P42300. 【模板】树套树2/Dynamic Rankings
【模板】树套树2/Dynamic Rankings
题目链接
题目描述
给定一个含有 个数的序列 ,需要支持两种操作:
Q l r k
表示查询下标在区间 中的第 小的数C x y
表示将 改为
输入格式
第一行两个正整数 ,表示序列长度与操作个数。
第二行 个整数,表示 。
接下来 行,每行表示一个操作,都为上述两种中的一个。
输出格式
对于每一次询问,输出一行一个整数表示答案。
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
3
6
提示
【数据范围】
对于 的数据,;
对于 的数据,;
对于 的数据,;
对于 的数据,,,,,。
请注意常数优化,但写法正常的整体二分和树套树都可以以大约 每个点的时间通过。
来源:bzoj1901
本题数据为洛谷自造数据,使用CYaRon耗时5分钟完成数据制作。