2020-2021:teams:die_java:front_page_treeintree
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:die_java:front_page_treeintree [2020/06/02 17:29] fyhssgss [例题 P3332 [ZJOI2013]K大数查询] |
2020-2021:teams:die_java:front_page_treeintree [2020/06/02 17:35] (当前版本) fyhssgss [例题 P3332 [ZJOI2013]K大数查询] |
||
|---|---|---|---|
| 行 105: | 行 105: | ||
| 让你维护一个有序数列，有以下操作： | 让你维护一个有序数列，有以下操作： | ||
| - | 1.查询k在区间内的排名 | + | 1.查询 $k$ 在区间内的排名 |
| - | 2.查询区间内排名为k的值 | + | 2.查询区间内排名为 $k$ 的值 |
| 3.修改某一位值上的数值 | 3.修改某一位值上的数值 | ||
| - | 4.查询k在区间内的前驱 | + | 4.查询 $k$ 在区间内的前驱 |
| - | 5.查询k在区间内的后继 | + | 5.查询 $k$ 在区间内的后继 |
| 就是平衡时问题加上了区间限制。我们外层建线段树，每一个节点维护该节点包含区间的平衡树。 | 就是平衡时问题加上了区间限制。我们外层建线段树，每一个节点维护该节点包含区间的平衡树。 | ||
| 行 119: | 行 119: | ||
| 操作一和操作三对线段树上包含区间的节点全部进行操作。 | 操作一和操作三对线段树上包含区间的节点全部进行操作。 | ||
| - | 操作四，五，外层线段树区间查询，对每个包含[l,r]的节点得到的前驱/后继求一个最大值/最小值即可。 | + | 操作四，五，外层线段树区间查询，对每个包含 $[l,r]$ 的节点得到的前驱/后继求一个最大值/最小值即可。 |
| 操作二 我们二分答案，和操作一类似，利用小于某数的个数进行二分。复杂度多一个 $log$ 。 | 操作二 我们二分答案，和操作一类似，利用小于某数的个数进行二分。复杂度多一个 $log$ 。 | ||
| 行 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]$ 范围内的数。 |
| 之所以这题不能像上文一样用线段树套平衡树（外层记录位置，内层维护权值）的原因是：对于套在外面那一层的线段树是很难进行区间操作的，所以这题就需要换一个思路，把位置信息放在内层的线段树中。 | 之所以这题不能像上文一样用线段树套平衡树（外层记录位置，内层维护权值）的原因是：对于套在外面那一层的线段树是很难进行区间操作的，所以这题就需要换一个思路，把位置信息放在内层的线段树中。 | ||
| 行 440: | 行 440: | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| - | 题目询问的是区间第$k$小 | + | 题目询问的是区间第 $k$ 小 |
| - | 如果不考虑区间，求第$k$小的话，用线段维护权值数量即可。求第$k$大只需在线段树上走，如果左区间权值和$L_v \geq k$，就往左走，否则往右走，直到一个叶子节点，即为答案。 | + | 如果不考虑区间，求第 $k$ 小的话，用线段维护权值数量即可。求第 $k$ 大只需在线段树上走，如果左区间权值和 $L_v \geq k$ ，就往左走，否则往右走，直到一个叶子节点，即为答案。 |
| - | 现在考虑区间，我们可以将线段树可持久化，就可以支持作差处理，如果要求一段区间$[l,r]$的第$k$小，我们只需在$r$处的线段树和$l - 1$处线段树作差后求出第$k$大。 | + | 现在考虑区间，我们可以将线段树可持久化，就可以支持作差处理，如果要求一段区间 $[l,r]$ 的第 $k$ 小，我们只需在 $r$ 处的线段树和 $l - 1$ 处线段树作差后求出第 $k$ 大。 |
| - | 如果还要支持单点修改，我们线段树的建立就不能单纯的在区间的基础上。如果仍然如此建树，则每次修改区间都要修改该点之后的线段树，数目是$O(n)$的。这个时候我们可以在树状数组的每个点上建树。如此，每个点有关的线段树只有$O(logn)$总复杂度降到$O(nlog^2n)$ | + | 如果还要支持单点修改，我们线段树的建立就不能单纯的在区间的基础上。如果仍然如此建树，则每次修改区间都要修改该点之后的线段树，数目是 |
| + | $O(n)$ 的。这个时候我们可以在树状数组的每个点上建树。如此，每个点有关的线段树只有 $O(logn)$ 总复杂度降到 $O(nlog^2n)$ | ||
| <hidden 代码查看> | <hidden 代码查看> | ||
2020-2021/teams/die_java/front_page_treeintree.1591090140.txt.gz · 最后更改: 2020/06/02 17:29 由 fyhssgss
