题解：P14447 [ICPC 2025 Xi'an R] Azalea Garden

· · 题解

题解 P14447

前置知识：线段树，multiset。

题目大意

已知 n 个不同的生物，每个生物有攻击值 a_i，防御值 b_i，你可以进行任意次操作，每次操作任意选择两个活着的生物 i 和 j，令 i 攻击 j，若 a_i\ge b_j，则 j 死亡。你需要求出最后活着的生物的数量的最小值。此外，有 q 次信息更改，每次更改后都要求解。

## 题目分析 观察每一次对战的过程，感性理解是攻击力越高越容易打死别人，所以猜测，如果有对战过程，一定都要让攻击力最高的人去打死别人。 那么找到攻击力最高的 $a_i$，那么对于 $b_j>a_i$ 的人一定死不掉，$b_j\le a_i$ 的人一定会被打死，设有 $x$ 个人死不掉，则答案的上界是 $x+1$，下界是 $x$。区别在于 $i$ 会不会被打死。 分类讨论。 * 若 $b_i>a_i$，则答案为 $x+1$，这种情况显然不存在能打死 $i$ 的。 * 优先从集合 $\{j~|~b_j>a_i\}$ 中找到攻击力最大的数，设为 $A$，若 $A\ge b_i$，则答案是 $x$。 * 否则尝试在集合 $\{j~|~b_j\le a_i\}$ 找到一条链 $k_{1\cdots m}$，使得 $a_{k_j}\ge b_{k_{j+1}}$，$A\ge b_{k_1}$，$a_{k_m}\ge b_i$，若能找到，答案是 $x$。其余情况答案均为 $x+1$。 如何判定这三种情况呢？前两种是简单的，只需要维护出全局 $a_i$ 最大的二元组 $(a_i,b_i)$，求出集合 $\{j~|~b_j>a_i\}$ 的大小，求出 $\max_{b_j>a_i} a_j$ 即可。前者用 multiset 维护，后两者本质是在线一维偏序，线段树轻松维护。 重点考虑第三种情况如何判定。 首先，存在合法构造方案使得链中不存在 $b_j\ge a_j$ 的元素，否则 $a_{k_{j-1}} \ge b_{k_{j}} \ge a_{k_{j}} \ge b_{k_{j+1}}$，则删去 $k_j$ 一定更不劣。 考虑把 $(a_j,b_j)$ 抽象成一条数轴上的区间 $[b_j,a_j]$，则你需要在满足 $b_j\le a_i$ 的 $j$ 中挑选若干个区间，使得 $[A,b_i]\sube \bigcup_{b_j\le a_i} [b_j,a_i]$。 考虑如何判定这一坨并集的东西，发现最大值变化时可用的区间集合是变化的，不好维护。寻找性质发现，如果我们提前把上面的情况一和情况二判断掉，把所有合法区间加入是不会影响答案的。考虑 $b_j>a_i$ 的区间 $[b_j,a_j]$，因为 $b_i\le a_i$，所以有 $a_j\ge b_j > a_i \ge b_i$，所以这些区间在数轴上一定位于 $b_i$ 的右侧，不影响区间 $[A,b_i]$ 的覆盖情况。 现在维护这个东西就简单了，等价于判断所有区间的并集是否能完整覆盖 $[A,b_i]$，离散化后用线段树维护每个区间的覆盖次数最小值即可。 时间复杂度 $O(n\log n)$，瓶颈是离散化和线段树。 实现的时候注意一些细节，这里列出几个。 * multiset 对于重复元素的删除操作不能使用 erase。 * 线段树不应维护点的覆盖，否则形如 $[1,2] \cup[3,4]$ 会被判定为 $[1,4]$。维护线段的覆盖。 * 数组开够大小，离散化后下标可达 $2n+2q$。 完结撒花。 谨遵指令之意。