bzoj 3110: [Zjoi2013]K大数查询 树套树

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


外层:权值线段树

内层:动态开点线段树

树套树,尽量养成好习惯,标记永久化…

每次进行插入的时候相当于在外层线段树上单点修改,然后对于走过的外层线段树的点的内层线段树进行区间修改

查询的时候,相当于在权值线段树上进行二分,如果右半边的,在询问区间内的点的个数>=c,那么就往右走,否则往左走,当l==r就是答案

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注