2020-2021:teams:die_java:front_page_treeintree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:die_java:front_page_treeintree [2020/06/02 17:35] fyhssgss [题解] |
2020-2021:teams:die_java:front_page_treeintree [2020/06/02 17:35] (当前版本) fyhssgss [例题 P3332 [ZJOI2013]K大数查询] |
||
|---|---|---|---|
| 行 339: | 行 339: | ||
| 有$N$个位置，$M$个操作，操作有2种。 | 有$N$个位置，$M$个操作，操作有2种。 | ||
| - | * 操作1：''%%1 a b c%%'' 在第$a$个位置到第$b$个位置，每个位置加入一个数$c$ | + | * 操作1：''%%1 a b c%%'' 在第 $a$ 个位置到第 $b$个位置，每个位置加入一个数$c$ |
| - | * 操作2：''%%2 a b c%%'' 询问从第$a$个位置到第$b$个位置中第$c$大的数。 $n,m\leq5*10^4,|c|\leq n$ | + | * 操作2：''%%2 a b c%%'' 询问从第 $a$ 个位置到第 $b$ 个位置中第 $c$ 大的数。 $n,m\leq5*10^4,|c|\leq n$ |
| === 题解 === | === 题解 === | ||
| - | 权值线段树套位置线段树。其中第一维记录权值，第二维记录位置。对于第一维线段树上的一个节点维护的权值区间$[L, R]$，它所指向的那颗线段树中记录的是每个位置包含了几个值在$[L, R]$范围内的数。 | + | 权值线段树套位置线段树。其中第一维记录权值，第二维记录位置。对于第一维线段树上的一个节点维护的权值区间 $[L, R]$ ，它所指向的那颗线段树中记录的是每个位置包含了几个值在 $[L, R]$ 范围内的数。 |
| 之所以这题不能像上文一样用线段树套平衡树（外层记录位置，内层维护权值）的原因是：对于套在外面那一层的线段树是很难进行区间操作的，所以这题就需要换一个思路，把位置信息放在内层的线段树中。 | 之所以这题不能像上文一样用线段树套平衡树（外层记录位置，内层维护权值）的原因是：对于套在外面那一层的线段树是很难进行区间操作的，所以这题就需要换一个思路，把位置信息放在内层的线段树中。 | ||
2020-2021/teams/die_java/front_page_treeintree.1591090507.txt.gz · 最后更改: 2020/06/02 17:35 由 fyhssgss
