题解：P15585 [KTSC 2026] 绝妙区间 2 / Wonderful Interval 2

· · 题解

孩子们，dmy 省选模拟赛搬这个我第一步转换都没出来。

首先有解的充要条件肯定是：\cup_{i=l}^r\left\{b_i\right\}\supset(\cup_{i=l}^r\left\{x\in\mathbb{Z}|a_i\leq x<b_i\right\})。

则有：|\cup_{i=l}^r\left\{b_i\right\}|=|\cup_{i=l}^r\left\{x\in\mathbb{Z}|a_i\leq x\le b_i\right\}|。

考虑反证法：若 |\cup_{i=l}^r\left\{b_i\right\}|\ne|\cup_{i=l}^r\left\{x\in\mathbb{Z}|a_i\leq x\le b_i\right\}|，则肯定是 \cup_{i=l}^r\left\{b_i\right\}\subseteq \cup_{i=l}^r\left\{x\in\mathbb{Z}|a_i\leq x\leq b_i\right\}。即 \exist l\le i\le r，使得 \left\{x\in\mathbb{Z}|a_i\leq x\leq b_i\right\}\not\subset\cup_{i=l}^r\left\{b_i\right\}，即 \cup_{i=l}^r\left\{b_i\right\}\not\supset\left\{x\in\mathbb{Z}|a_i\leq x<b_i\right\}，假设不成立。

即需维护区间元素种类数和区间线段并的大小，P1972 和 P8512 的代码拼起来即可，复杂度为 O(n+q\log n)。通过一些科技手段可以抢夺最优解。