ABC389F

· · 题解

  • 给出 n 个区间 [L_i,R_i]，定义函数： f(X,i)=\begin{cases}X,i=0\\f(X,i-1)+1,i\ne 0\land f(X,i-1)\in[L_i,R_i]\\f(X,i-1),\text{otherwise}\end{cases}

注意到 f(X,i) 非降。给出证明：

考虑归纳法。

  • 当 i=0 时显然非降。
  • 假设当 i\in [0,m] 时非降，则当 i=m+1 时，记最小、最大的满足 f(X,m)\in[L_{m+1},R_{m+1}] 的 X 分别为 X_{\min},X_{\max}，则由于非降的性质，f(X,m)\in[L_{m+1},R_{m+1}] 的 X 构成的集合等价于区间 [X_{\min},X_{\max}]，且 f(X_{\max}+1,m)>f(X_{\max},m)。则对于这个区间内的数 X 而言，f(X,m+1)=f(X,m)+1，剩余 X 的 f(X,m+1)=f(X,m)。由于当 i=m 时 f(X,i) 非降，因此对于 [1,X_{\min}),[X_{\min},X_{\max}],(X_{\max},+\infty) 三个区间而言，其内部的 f(X,m+1) 非降。且有 f(X_{\min}-1,m)\le f(X_{\min},m)<f(X_{\min},m)+1，f(X_{\max},m)+1=f(X_{\max},m+1)\le f(X_{\max}+1,m+1)。从而证明了临界点处非降。因此当 i\in[1,m+1] 时 f(X,i) 非降。
\mathcal{Q.E.D.}

然后就简单了。枚举 i 维护当前的 f(X,i)，根据单调性可以二分出每次的 X_{\min},X_{\max}，然后区间加即可从 f(X,i) 推到 f(X,i+1)。二分的检查以及询问均需要支持单点查询，使用 BIT 维护差分数组即可。

时间复杂度 \mathcal{O}\left(n\log^2 X\right)，空间复杂度为 \mathcal{O}(X)。

AC Link & Code