有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c
如果是2 a b c形式,表示询问从第a个位置到第b个位置,第C大的数是多少。
树套树专题——bzoj 3110: [Zjoi2013] K大数查询 & 3236 [Ah
发布时间:2020-12-14 03:35:59 所属栏目:大数据 来源:网络整理
导读:【原题1】 3110: [Zjoi2013]K大数查询 Time Limit:? 20 Sec?? Memory Limit:? 512 MB Submit:? 978?? Solved:? 476 Description 有N个位置,M个操作。操作有两种,每次操作如果是1 a b c的形式表示在第a个位置到第b个位置,每个位置加入一个数c 如果是2 a b
【原题1】 3110: [Zjoi2013]K大数查询Time Limit:?20 Sec?? Memory Limit:?512 MBSubmit:?978?? Solved:?476 DescriptionInput第一行N,M
接下来M行,每行形如1 a b c或2 a b c Output输出每个询问的结果
Sample Input
2 5
1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 2 1 2 3 Sample Output1 2 1 HINT
【传送门】感谢这位大牛给我的启发。http://www.cnblogs.com/lazycal/archive/2013/08/05/3239304.html 【分析】一直听到过有一种神奇的数据结构——树套树。于是通过这道题我开始接触这种算法。 树套树的本质就是两棵树套在一起(一般最外层的都是线段树)。对于当前的这棵树的每个结点可以再开一棵树来维护。因为会爆内存,所以注意要动态开结点。说起来有点玄乎,先看看这道题吧。 我们可以先开一颗权值线段树。对于当前结点K,它表示了权值范围为a~b的所有结点的信息。但是有人要问:这样怎么控制位置范围是l~r这个要求呢?我们可以在这个点上再开一棵 |