11.3

杂题。

CF1601D Difficult Mountain

考虑 Exchange Argument。

按照 \(\max(a_i,s_i)\) 从小到大排序，相同的按照 \(s_i\) 从小到大排序。这样做的正确性有保证。

  • 若 \(\max(a_i, s_i) = s_i\)，则 \(i\) 一定能爬上去，对答案不影响。
  • 若 \(\max(a_i,s_i) = a_i\)，这个东西一定是类似于一段前缀的。显然无论你选择哪一个在第一个位置，山的高度都会变成 \(a_i\)，所以对答案不影响。

排序后按照题目模拟即可。

QOJ1429

对于区间选点有经典贪心：按照右端点从小到大排序，从左往右尝试选点，若当前区间未被覆盖，则选中当前区间的右端点。

对于此构造可以求出目前的被覆盖次数的最大值 \(t\)，声称最终的答案只会是 \(t\) 或者 \(t-1\)。

设当前最多选中区间为 \([L,R]\)，则被覆盖的一定是 \(i\in S,[l_i,r_i]\) 满足 \(S\) 中的区间两两无交。显然要减少次数，只能将最前面的一个尝试前移。

具体地，先只判定上界 \(K=t-1\) 是否可行。若 \(t=1\) 直接输出原贪心。把区间 \([l_i,r_i]\) 改写成半开区间 \([l_i,r_i+1)\)，收集所有 \(l_i,r_i+1\) 离散化为

\[d_1

真实候选状态为 \(1,\dots,M-1\)，状态 \(j\) 对应坐标 \(d_j\)；\(0\) 是左侧虚拟状态，\(M\) 是右侧终止状态。原区间变成离散下标区间 \([L_i,R_i]\)。

对每个边界 \(i\) 预处理

\[A_i=\max\{L_j\mid R_j

\(A_i\) 用于找前驱：若要把 \(i\) 接在 \(q\) 后面，必须 \(q\ge A_i\)，否则会有区间完全落在 \(q,i\) 之间而漏覆盖。\(B_i\) 用于容量检查。

从左往右维护合法真实状态数组 legal，初始为 \([0]\)。对每个真实状态 \(i\)，在 legal 中二分找到第一个 \(q\ge A_i\)，令

\[\operatorname{pred}(i)=q. \]

若找不到，则 \(i\) 不合法。找到后建倍增表

\[up[i][0]=\operatorname{pred}(i),\qquad up[i][j]=up[up[i][j-1]][j-1], \]

并求

\[y=\operatorname{pred}^{(K)}(i). \]

若 \(y，说明加入 \(i\) 后所有包含 \(i\) 的区间仍至多含 \(K\) 个链上点，\(i\) 合法，加入 legal；否则 \(i\) 不合法。由于 \(A_i\) 单调，一旦找不到前驱，后面也不可能成功，可直接判 \(K\) 不可行。

最后检查终止边界 \(M\)：在 legal 中找第一个 \(q\ge A_M\)。找不到则 \(K=t-1\) 不可行，输出答案 \(t\) 和最初的右端点贪心方案；找到则从 \(q\) 沿 pred 一路回溯到 \(0\)，反转后把每个状态 \(j\) 映射为坐标 \(d_j\)，即为答案 \(K\) 的构造。

正确性核心是：最小合法前驱不会丢解；若存在上界 \(K\) 的方案 \(p_1<\cdots，归纳有 \(\operatorname{pred}^{(h)}(p_j)\le p_{j-h}\)，因此算法不会把方案点误判为不合法；终止前驱 \(q\ge A_M\) 保证所有右端落在 \([q,M)\) 的区间被 \(q\) 覆盖，已结束区间由前驱链覆盖，容量检查又保证每区间至多 \(K\) 个点。构造点数不超过 \(n\)：每个链点都能找到一个只包含它的见证区间，不同链点见证区间不同。