主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
数据结构做题记录
最后更新于 2025-06-16 10:32:41
作者
liaoyichen
分类
个人记录
复制 Markdown
查看原文
更新内容
[CF1849E Max to the Right of Min](https://www.luogu.com.cn/problem/CF1849E) 套路的枚举区间最大值的位置，记为 $i$，预处理 $i$ 左边第一个比它大的位置 $l$、右边第一个比它大的位置 $r$。先处理有一个端点是 $i$（一定是右端点）的区间，有 $i - l - 1$ 个。 考虑一种方法：枚举左端点 $j$，$l + 1\le j \le i - 1$，从右往左扫，边扫边记录区间 $[j, i - 1]$ 的最小值的位置，记为 $pos$ ，我们想让 $pos$ 成为区间的最小值（只有这样才能满足最小值在最大值左边），找到 $pos$ 右边第一个比 $pos$ 小的位置 $rp$，那么区间右端点最多可以到 $rp - 1$，区间数有 $rp - 1 - i$ 个（有个细节就是 $rp - 1$ 最大取到 $r - 1$）。 还有另一种方法：枚举右端点 $j$，$i + 1\le j \le r - 1$，从左往右扫，边扫边记录区间 $[i + 1, j]$ 的最小值的位置，记为 $pos$，我们不能让 $pos$ 成为区间最小值，要让 $i$ 左边有比 $pos$ 更小的值 ，找到 $pos$ 左边第一个比 $pos$ 小的值 $lp$，区间左端点至少要取到 $lp$，区间数为 $lp - (l + 1) + 1 = lp - l$（有个细节 $lp$ 最小取到 $l$）。 现在考虑结合这两种做法，如果枚举左端点的次数比枚举右端点少，采用第一种方法，否则第二种。这个东西叫启发式分裂，每个点最多被枚举到 $O(\log n)$ 次，总复杂度 $O(n \log n)$。 感性证明一下：考虑钦定枚举 $i$ 时按照 $a_i$ 从大往小枚举，每次将 $i$ 标记，那么每次找 $l$、$r$ 其实就是找左边第一个有标记、右边第一个有标记的，考虑你枚举了其中一个区间，这个区间肯定小于 $[l + 1, r - 1]$ 的一半，然后你把 $i$ 标记，下次你枚举到那个区间中的某个数时枚举量肯定小于等于那个区间的一半。换句话说，如果一个位置相邻 $2$ 次被 $2$ 个区间给枚举到了，后面这个区间的大小最多是前面那个区间大小的一半,首先区间大小一定变小了，且这一次又在前面那个区间中打了一个标记，挑选更小的区间，所以最多一半，每个位置最多被枚举到 $O(\log n)$ 次。建议自己画个图理解一下。 ------------ [P9478 [NOI2023] 方格染色](https://www.luogu.com.cn/problem/P9478) 考虑没有斜线怎么做，先把有交的横线都合并起来，有交的竖线都合并起来，计算格子数，然后考虑把横竖交点个数减掉。将横线的纵坐标、竖线上下端点的纵坐标离散化，然后扫描线：按照竖线横坐标排序，每次碰到横线左端点将横线的纵坐标加入；碰到横线右端点的右边，将横线纵坐标删除。然后求竖线上下端点纵坐标之间的区间和，树状数组即可。 现在有了斜线，先将斜线合并。考虑减掉斜线与横线的交点，枚举横线，将斜线和横线看成直线求交点，看交点是否在横线上即可。现在还差一部分贡献没有减掉：竖线与斜线的交点，且没有横线经过，考虑在前面扫描线的时候同时做这件事情，求出竖线所在直线与斜线所在直线的交点，如果交点在竖线上，且没有横线经过，就减掉 $1$，复杂度大常数 $O(n \log n)$。 ------------ [P3582 [POI2015] KIN](https://www.luogu.com.cn/problem/P3582) 记录 $nex_i$ 为 $i$ 右边第一个 $j$ 满足 $f_i = f_j$。考虑从右往左枚举区间的左端点 $l$，假设左端点为 $l + 1$ 时，右端点为 $[l + 1, n]$ 的答案分别记录在线段树下标为 $[l + 1, n]$ 的位置。 - 现在考虑右端点在 $[l + 1, nex_l - 1]$ 的区间，新的答案就是原来的答案加上 $w_{f_l}$（这些区间第一次出现 $f_l$）。 - 右端点在 $[nex_l, nex_{nex_l} - 1]$，这些区间已经有恰好一个 $f_l$ 了，新的答案在原来答案基础上减去 $w_{f_l}$。 - 右端点在 $[nex_{nex_l}, n]$，这些区间至少有 $2$ 个 $f_l$，再多出一个 $f_l$ 答案不变。 - 右端点是 $l$，答案为 $w_{f_l}$，记得在线段树上更新。 综上，要实现区间加，区间最值，复杂度大常数 $O(n \log n)$。（有一些细节，比如 $nex_l$，$nex_{nex_l}$ 不存在）。 ------------ [P1972 [SDOI2009] HH的项链](https://www.luogu.com.cn/problem/P1972) 莫队要卡常。离线下来所有询问，按照 $r$ 从小到大排序，从左往右扫，用一棵树状数组，如果目前有多个相同元素，将最后一个元素的下标在树状数组上加 $1$，询问树状数组上 $[l, r]$ 的和即可。正确性：如果一种元素出现在区间中，那它最后一次出现肯定在区间中，每种元素最多标记一个位置，区间中任何标记 $1$ 的位置都代表一种元素。复杂度 $O(n \log n)$。 ------------ [ CF848C Goodbye Souvenir](https://www.luogu.com.cn/problem/CF848C) 带修莫队 $O(n^{\frac{5}{3}} \log n)$ 要卡常。 记 $pre_i$ 为 $i$ 前面第一个 $j$ 使得 $a_i = a_j$，我们要求的柿子其实是 $\sum_{i = l}^{r} [pre_i \ge l] \times (i - pre_i)$，因为如果 $i \le l - 1$，$pre_i \le l - 1$，所以上式可以简化为 $\sum_{i = 1}^{r} [pre_i \ge l] \times (i - pre_i) $，这就是个标准的二维数点。 具体的，$pre_i$ 为横坐标，$i$ 为纵坐标，点权为 $i - pre_i$，询问形如求 $x \ge l$ 且 $y \le r$ 的点权和。 但是这题带修，所以我们考虑加一个维度时间维，转化为三维偏序（用 set 维护 $a_i$ 相同的所有 $i$，提前预处理好将修改转化为 $O(1)$ 个加点、删点），cdq 分治，归并按照 $x$ 从大到小排序，边归并边用个树状数组维护即可。 复杂度 $O(n \log^2 n)$。 ------------ [P2824 [HEOI2016/TJOI2016] 排序](https://www.luogu.com.cn/problem/P2824) 只有一个询问非常神秘，考虑二分。我们每次二分是否有 $ans \ge mid$，构造一个 01 序列 $b$，$\forall i \in [1, n], b_i = [a_i \ge mid]$，对于这个 01 序列 $b$ 按照那些操作排序，显然可以做到 $O(n \log n)$，最后 check 一下是否有 $b_p = 1$，正确性在于对于 $\ge mid$ 和 $< mid$ 的数，在 $b$ 序列中它们 $2$ 个集合之间的元素的相对关系不会改变。 复杂度 $O(n \log^2 n)$。 ------------ [CF1709E XOR Tree](https://www.luogu.com.cn/problem/CF1709E) 先做个树上前缀异或和，记 $d_i$ 为根节点到 $i$ 的路径上点权异或和，两点之间的路径异或和即为 $d_x \oplus d_y \oplus a_{lca(x, y)}$。 我们考虑如果修改一个点的点权，那么可以修改为一个极大值，使得所有经过这个点的路径异或和均不为 $0$。 对于每个点，记录一个 set 保存子树中所有点的 $d$ 值，如果存在 $2$ 个点的 $d$ 值异或为 $a_x$，那么就得修改 $a_x$，同时这个子树中的点就和外面隔离开来（修改点权相当于删去这个点），因为子树中的点和子树外的点的路径必经 $x$，这条路径一定非 $0$，此时把 $x$ 的 set 清空。 本质是个贪心，假如现在有 $2$ 条都是异或和为 $0$ 的路径，它们有交点，深度大的 lca 一定在 lca 深度小的路径上，此时我们修改深度大的 lca 一定最优（同时将 $2$ 条路径都变成异或和非 $0$），所以策略是先遍历子树，让每个子树内部路径都非 $0$（如果一个点修改了，它的子树的信息就不用了，原因见上一段），然后合并这些子树的信息，来判断 $x$ 有没有必要修改。 具体实现上，维护 set 可以用启发式合并，记得要清空 set。时间复杂度 $O(n \log^2 n)$。 ------------ [CF1641C Anonymity Is Important](https://www.luogu.com.cn/problem/CF1641C) 线段树解法比较平常，基于一个性质：判断一个人没患病，当且仅当有至少一个 $1$ 类区间覆盖到了；判断一个人患病了，当且仅当存在至少一个 $2$ 类区间包含他，且这个区间除他外的所有人都判断出没有患病。然后把所有信息读进来，先判断是否患病（线段树维护一个区间和即可），再算出最早什么时候能够判断出来： - 算出没患病的，倒序遍历 $1$ 类区间，做个区间覆盖。 - 算出患病的，对于每一个判断出他患病的 $2$ 类区间，设这个 $2$ 类区间给出的时间为 $t_1$，然后算出这个区间其他人（都是没患病的）最晚确定没患病的时间 $t_2$，$2$ 者取个 $\max$ 就是用这个区间来判断这个人患病的最早时间。对于所有能够判断出他患病的 $2$ 类区间，答案再取个 $\min$。 上面这个做法太复杂了，看个稍微简单一点的。 在线做法，先开一棵线段树对于每一个 $1$ 类区间执行区间加。 - 判断 $i$ 没患病，该位置 $\ge 1$。 - 判断 $i$ 患病，求出一个最小的 $l$ 使得 $[l, i - 1]$ 都没患病，求出一个最大的 $r$ 使得 $[i + 1, r]$ 都没患病，检验是否有 $2$ 区间在 $[l, r]$ 中即可（这个 $2$ 区间一定包含 $i$，否则信息自相矛盾）。对于检验操作，再开一棵线段树，$x$ 位置保存最小的 $y$ 使得有 $2$ 类区间 $[x, y]$（否则为正无穷），检验就看这个线段树上 $[l, r]$（或者说 $[l, i]$ 也对，因为 $i \le y \le r$ 一定有 $l \le x \le i$） 的最小值是否 $\le r$ 即可。 上面这个做法也复杂了，看个更简单的。 考虑用并查集实现第二个方法。 用并查集维护连通块。对于一个一类区间 $[l, r]$，在并查集中把 $[l, r + 1]$ 合并，同时将 $r + 1$ 作集合代表元素，把编号小者合并到编号大者集合内；同时维护 $\forall i \in [l, r + 1]$，若 $i$ 为一个有病者区间的左端点，则右端点的最小值，此值在连通块最右端（集合代表元素）处更新。 - 判断没患病的充要条件就是他不是集合代表元素（根据合并方法可知，当且仅当没患病才会被合并，被合并的一定没患病）。 - 判断患病，首先他是集合代表元素，其次他的集合的值（上文更新的值，其实就是上文第二棵线段树在 $[l, i]$ 处的最小值）小于右边连通块的代表元素（其实是上文的 $r + 1$）。 可以看到，并查集解法本质和第二种解法一模一样，不过采用了并查集维护，均摊可知总共有 $O(n)$ 次查询、合并操作，总复杂度 $O(n \log n)$。 ------------ [P4587 [FJOI2016] 神秘数](https://www.luogu.com.cn/problem/P4587) 考虑一个暴力，维护一个可重集，假设之前的数可以表示出 $[1, ans]$，从小到大往可重集里插入数 $x$： - Case 1：$x \ge ans + 2$，因为 $x$ 后面要插入的数都 $\ge x$，所以 $ans + 1$ 一定表示不出来，$ans + 1$ 即为答案。 - Case 2： $x \le ans + 1$，每一个表示出 $[1, ans]$ 的方案加入 $x$ 都可以组出新的，并且一定包含 $[ans + 1, ans + x]$，新的可以表示的区间为 $[1, ans + x]$。 现在考虑用主席树优化，目前表示出的区间为 $[1, ans]$，考虑未插入的所有 $x$ 满足 $x \le ans + 1$，都可以使得答案上界增加 $x$，并且 $x$ 仍然满足 $x \le ans' + 1$，所以这些 $x$ 可以打包一起处理，一次性让 $ans$ 加上这些未插入且 $x \le ans + 1$ 的 $x$ 之和。考虑到原来插入进去的 $x$ 都满足 $x \le ans + 1$（从小到大枚举），这一次将未插入的所有 $\le ans + 1$ 的 $x$ 都插入了。其实只用求所有小于等于 $ans + 1$ 的 $x$ 的和就是新的上界，这一点归纳可证。当然如果这个和等于 $ans$ 的话 $ans + 1$ 就是最终答案。 复杂度分析暂时还不会，似乎可以分析出迭代次数在 $O(\log \sum a)$ 左右，总复杂度就是 $O(n \log n \log \sum a)$。 ------------ [P5068 [Ynoi2015] 我回来了](https://www.luogu.com.cn/problem/P5068) 输出的答案就是对于每一种伤害 $L \le d \le R$，伤害触发的次数和（有个细节，每种伤害至少触发第一次）。 考虑伤害为 $d$，我们关心是否存在血量为 $[1, d]$，$[d + 1, 2 \times d]$，$\dots$，$[d \times \left \lfloor \frac{n}{d} \right \rfloor + 1, n]$ 的随从，我们记 $(d, i)$ 表示伤害为 $d$ 的第 $i$ 个区间，总区间个数在 $O(n \log n)$ 量级。 如果将操作离线，我们记 $t_{d, i}$ 表示区间 $(d, i)$ 最早出现随从是在哪个操作后，如果记录血量 $i$ 的随从最早在 $a_i$ 个操作后出现（不存在记为正无穷），那么 $t_{d, i}$ 就是 $(d, i)$ 这段区间中 $a_i$ 的最小值，可以 $O(n \log n)$ 预处理得到所有的 $t_{d, i}$。 然后考虑记 $f_{d, i}$ 表示伤害值为 $d$ 能够至少触发 $i$ 次（不算初始第 $1$ 次）的最早时刻，那么有 $f_{d, i} = \max(t_{d, j}) (1 \le j \le i)$，改变一下形式有 $f_{d, i} = \max(f_{d, i - 1}, t_{d, i})$，这个也可以 $O(n \log n)$ 预处理。 对于时刻大于等于 $f_{d, i}$ 且 $L \le d \le R$ 的询问 $[L, R]$，区间 $(d, i)$ 对其有 $1$ 的贡献，这个东西用个树状数组即可。 总复杂度 $O(n \log^2 n)$。 ------------ [ CF650D Zip-line](https://www.luogu.com.cn/problem/CF650D) 经典结论： - 对于最长严格上升子序列（LIS），我们常常记强选第 $i$ 个数前 $i$ 个数的 LIS 为 $f_i$，强选第 $i$ 个数后 $i$ 个数的 LIS 为 $g_i$，如果 $f_i + g_i - 1 = ans$， $i$ 在某些 LIS 中（显然一个序列可以有多个 LIS），且 $i$ 一定在 LIS 的第 $f_i$ 位（考虑反证）。所以得到判断 $i$ 是否是 LIS 的必经点的充要条件：$f_i + g_i - 1 = ans$ 且 对于 $f_i + g_i - 1 = ans$ 的所有点不存在除 $i$ 之外的一个 $j$ 满足 $f_i = f_j$。 同样的，我们先求出 $f$ 和 $g$ 数组，记未修改的 LIS 长度为 $lans$。 - Case 1：修改的位置 $i$ 在新的 LIS 上，修改后的值为 $v$，那么这种情况答案为 $\max(f_j + 1 + g_k) (j < i < k, a_j < v < a_k)$。 - Case 2：$i$ 是 LIS 的必经点，这种情况新的 LIS 为 $lans - 1$；否则为 $lans$。 根据经典结论，整个问题时间复杂度 $O(n \log n)$。 ------------ [CF1614E Divan and a Cottage](https://www.luogu.com.cn/problem/CF1614E) 用线段树维护下标为初始温度时现在的温度为多少。维护一个 $maxn$ 和一个 $minn$ 分别表示当前区间现在温度最大值和最小值。 今天的气温为 $t$，线段树遍历下去： - Case 1：$maxn < t$，这个区间全体加 $1$，返回。 - Case 2：$minn > t$，这个区间全体减 $1$，返回。 - Case 3：$minn = t = maxn$，直接返回。 - Case 4：剩余情况递归到左右儿子。 这个做法看着很暴力，我们来分析一下复杂度。首先容易知道现在温度和初始温度有单调性，所以现在温度相同且等于 $t$ 的一定是一段连续的区间（Case 3），同样的，Case 1 和 Case 2 也分别是连续的区间，本质上上面遍历的操作可以拆分成 $3$ 次对于 $3$ 段连续区间的修改操作，复杂度即为 $O(\log 10^9)$。总复杂度 $O(n \log 10^9)$. ------------ [P5072 [Ynoi2015] 盼君勿忘](https://www.luogu.com.cn/problem/P5072) 假设在一个长度为 $t$ 的序列中，数字 $x$ 出现了 $k$ 次，那么它的贡献就是 $(2^t - 2^{t - k}) \times x$。也就是说对于 $x$ 来说它的贡献只跟区间长度还有它的出现次数有关，根据乘法结合律，我们把出现次数相同的 $x$ 放在一起计算答案，有个经典结论是对于长度为 $n$ 的序列，元素的出现次数的种类上界是 $O(\sqrt{n})$（自然根号）。 所以我们维护每个元素的出现次数，出现次数相同的元素之和，有哪些出现次数就可以跑莫队了，其中第三个东西可以用个链表或者 unordered_set 维护（卡卡常）。 不过有个新的问题，如果我们用快速幂计算 $2$ 的多少次方复杂度会多个 $\log$，怎么 $O(1)$ 算一个 $2$ 的多少次方呢？考虑光速幂，记 $t = \left \lfloor \sqrt{n} \right \rfloor$，预处理 $2^1$，$2^2$，$2^3$，$\dots$，$2^t$，$2^{2 \times t}$，$2^{3 \times t}$，$\dots$，$2^{t \times t}$ 的值，就可以 $O(1)$ 计算了，光速幂的本质是一种根号平衡。 整个问题用 $O(n \sqrt{n})$ 解决了。 ------------ [P3224 [HNOI2012] 永无乡](https://www.luogu.com.cn/problem/P3224) 线段树合并的板子题，时间复杂度 $O(n \log n)$，空间复杂度 $O(n \log n)$。 也可以平衡树启发式合并，把小的平衡树的元素一个个暴力插入大的平衡树，时间复杂度 $O(n \log^2 n)$，空间复杂度 $O(n)$。 ------------ [P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633) 对于每个点开一棵主席树记录根节点到该点的路径上的点权，查询的时候将主席树做 $t_x + t_y - t_{lca(x, y)} - t_{fa_{lca(x, y)}}$ 同时线段树上二分即可。 复杂度 $O(n \log n)$。 ------------ [P2839 [国家集训队] middle](https://www.luogu.com.cn/problem/P2839) 二分答案，check 是否有 $ans \ge mid$，构造序列 $b$，$\forall i \in [1, n],b_i = [a_i \ge mid]$，问题转化为是否存在区间 $[l, r]$ 满足 $a \le l \le b$ 且 $c \le r \le d$ 且 $\sum_{i = l}^{r}b_i \ge 0$。再进一步转化为区间 $[a, b)$ 的最大可空后缀和加上区间 $[b, c]$ 的和加上区间 $(c, d]$ 的最大可空前缀和是否大于等于 $0$。直接对于每个 $mid$ 都建一棵线段树空间复杂度爆炸，考虑到按照 $mid$ 从小到大建树，相邻 $2$ 棵树最多改变一个叶子的值，主席树即可。 有个细节在于相等的元素不用特殊处理，容易证明不会影响二分正确性。复杂度 $O(n \log^2 n)$。 ------------ [P3168 [CQOI2015] 任务查询系统](https://www.luogu.com.cn/problem/P3168) 将优先级离散化之后作为下标建立主席树，把任务拆成 $2$ 个单点加就可以了，询问直接在主席树上二分。复杂度 $O(n \log n)$。 ------------ [P3293 [SCOI2016] 美味](https://www.luogu.com.cn/problem/P3293) 求最大异或，考虑按位贪心。假设现在处理到第 $i$ 位（最低位是第 $0$ 位），只考虑 $b$、$a_j$ 的前面的位（把 $b$、$a_j$ 第 $i$ 位及之后全部抹去）使得 $b \oplus (a_j + x)$ 最大的 $a_j + x$ 是 $ans$。 - Case 1：$b$ 的第 $i$ 位是 $1$，我们想尽量让新的 $ans$ 第 $i$ 位为 $0$，查询区间中是否有 $[ans - x, ans + 2^ i - x - 1]$（这些数加上 $x$ 之后得到的和，第 $i$ 位是 $0$，并且 $i$ 前面的位和原来的 $ans$ 一样），如果有，代表存在至少一个 $a_j$ 使得不仅满足前面贪心的条件，而且 $a_j + x$ 的第 $i$ 位为 $0$，此时 $ans$ 不变，否则 $ans$ 加上 $2 ^ i$。 - Case 2：$b$ 的第 $i$ 位是 $0$，我们想尽量让新的 $ans$ 第 $i$ 位为 $1$，查询区间中是否有 $[ans - x + 2 ^ i, ans - x + 2 ^ {i + 1} - 1]$（这些数加上 $x$ 之后得到的和，第 $i$ 位是 $1$，并且 $i$ 前面的位和原来的 $ans$ 一样），如果有，代表存在至少一个 $a_j$ 使得不仅满足前面的贪心条件，而且 $a_j + x$ 的第 $i$ 位为 $1$，此时 $ans$ 加上 $2 ^ i$，否则 $ans$ 不变。 最后输出 $ans \oplus b$ 即可。我们发现查询操作可以用一棵主席树完成，本质上就是不改变前面得到的结果，尽量的使这一位的异或值为 $1$，原因在于异或是不进位加法，每一位之间隔离开，并且 $2 ^ i - 1 = \sum_{j = 0}^{i - 1} 2 ^ j$，也就可以从高到低贪心了。时间复杂度 $n \log^2 n$。 ------------ [P3402 可持久化并查集](https://www.luogu.com.cn/problem/P3402) 可持久化并查集，维护每个点的父亲，集合代表元素处维护集合大小，采用按秩合并（按集合大小合并）即可。复杂度 $n \log^2 n$。 虽然可持久化并查集可以拿来实现可撤销并查集，但是可撤销并查集只要用个栈就可以 $O(n \log n)$ 实现了。 ------------ [P4768 [NOI2018] 归程](https://www.luogu.com.cn/problem/P4768) 假如目前的水位线是 $x$，所有海拔 $> x$ 的边构成的连通块内都可以开车随意到达，所以整个连通块内所有的点的答案都是连通块内每个点到 $1$ 的最短路的最小值。 我们考虑先预处理出起点为 $1$ 的最短路，然后将边按照从大到小加入，合并连通块并且计算每个连通块的答案，就能得到只有海拔前 $i$ 大的边构成的并查集了，可持久化一下就可以得到任意有海拔前 $i$ 大边的版本的并查集。查询的时候二分出水位为 $x$ 时有海拔前 $i$ 大的所有边，找到对应版本的并查集查询即可。 复杂度 $O(n \log^2 n)$。 还有一个解法是 Kruskal 重构树，考虑从大到小加入边，如果找出了不同的两个连通块的代表元素，我们在重构树上新建一个点作为两个代表元素的父亲，并将当前边的边权转化为新点的点权。 我们发现重构树上所有叶子结点恰好对应原图上的点，并且根节点到某个叶子结点的路径上，点权单调递增。 所以我们得到了性质：如果重构树上某个非叶子结点的点权为 $x$，并且 $x$ 大于水位线，则这棵子树中所有的叶子结点都可以开车互相到达，可以类比上一种做法中在当前水位线版本，这个子树内的点位于同一个并查集；如果这个点的父亲的点权为 $y$，$y$ 小于等于水位线，则 $x$ 子树内的点到子树外的点必须要步行，相当于上一个做法中，当前水位线版本的一个极大并查集，一个简单的证明在于 $y$ 一定是这棵子树内的点连接到子树外的点的边当中边权最大的，这一点由重构树构造方式可知。 所以如果我们查询一个点 $p$，水位线为 $x$，就倍增查询找到 $p$ 的某个祖先 $q$，满足 $q$ 的点权大于 $x$，$q$ 的父亲的点权小于等于 $x$，在这个水位线的情况下，$q$ 子树都可以开车互相到达，想要出 $q$ 子树必须步行，答案即为这个子树内的叶子结点到 $1$ 最短路的最小值。 复杂度 $O(n \log n)$。 ------------ [P4169 [Violet] 天使玩偶/SJY摆棋子](https://www.luogu.com.cn/problem/P4169) 分类讨论去掉绝对值号，静态是个显然的二位数点，动态就是三维偏序。 我们设统计的时候参照物的点是 $A$，统计的点是 $B$，实现上只要写一种情况就好了（例如 $X_B \le X_A,Y_B \le Y_A$），其他情况可以通过左右翻转所有点（每个点的新横坐标变成 $10^6 + 5$ 减去原来的横坐标，相当于统计右下角，$X_B \ge X_A,Y_B \le Y_A$ 的所有点）、上下翻转所有点（新纵坐标变成 $10^6 + 5$ 减去原来的纵坐标，相当于统计左上角）、同时左右、上下翻转（相当于统计右上角）。时间复杂度 $O(n \log^2 n)$。 ------------ [P4755 Beautiful Pair](https://www.luogu.com.cn/problem/P4755) 统计区间数考虑分治，找到当前区间的最大值所在位置，记为 $p$，统计所有在当前区间内且包含 $p$ 的区间，然后继续分治到 $p$ 左边、$p$ 右边（统计不包含 $p$ 的区间，有个细节是长度为 $1$ 的区间）。 显然存在一种策略统计包含 $p$ 的区间：枚举左端点，统计区间个数形如查询在 $p$ 的右边（包含 $p$）一直到区间右端点有多少个小于等于某个数的数，这个可以用主席树，当然值域有点大要离散化，枚举右端点同理。 考虑每次枚举区间小的部分，显然每个点被枚举到时整个枚举的区间最大是上一次被枚举到时整个枚举区间的一半，枚举到 $O(\log n)$ 次，总复杂度 $O(n \log^2 n)$。
正在渲染内容...
点赞
1
收藏
0
