BZOJ 3110 [Zjoi2013]K 大数查询

发布于 2017-11-15  261 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3110

题意:有 N 个位置,M 个操作。操作有两种:

每次操作如果是 1 a b c 的形式表示在第 a 个位置到第 b 个位置,每个位置加入一个数 c
如果是 2 a b c 形式,表示询问从第 a 个位置到第 b 个位置,第 C 大的数是多少。


可以整体二分做,但是当树套树练手题写了... 人生中的第一次树套树大概...

由于此题有位置和权值两个信息需要维护,可以考虑使用树套树,内外层分别维护一个信息。

外层权值线段树维护权值,这个可以开满,是 O(n) 的。

内存普通线段维护区间和,为了空间能够接受需要动态开点。

对于操作 1,由于加的权值是一样的,直接对于外层一条链上的内层树暴力修改即可。

对于操作 2,从外层根节点出发以类似平衡树的方式查询。

坑点:

50000*50000 会爆 int,需要使用 unsigned int(同时卡常

读入数据有负数,需要将区间转化为正整数便于处理

 


一个非常弱的准退役OIER