WC2024

最简单的一届 WC。

P10143 [WC2024] 代码堵塞

难度：1

拆贡献，考虑 \(i\) 选 \(0\) 还是 \(1\)：

• 如果 \(i\) 选 \(0\)，那么它前面选 \(0\) 的加上它不超过 \(T\)。
• 如果 \(i\) 选 \(1\)，那么它后面选 \(0\) 的加上它和它前面的所有数不超过 \(T\)。

随便背包可以做到 \(\mathcal{O}(nT)\)。

P10144 [WC/CTS2024] 水镜

难度（算法一）：4

难度（算法二）：5

先考虑如何在 \(L\) 确定的时候如何判断合法，以下默认 \(h_i\neq h_{i+1}\)。

注意到 \(h_i\) 的两个取值必有一个不小于 \(L\)，且另一个不大于 \(L\)。我们不妨设 \(a_i=\min(h_i,2L-h_i)\)，那么必然是一个前缀取 \(a_i\)，一个后缀取 \(2L-h_i\)。则合法当且仅当 \(a_i\) 单峰，即 \(a_1<\cdots a_{k-1}<a_k>a_{k+1}>\cdots >a_n\)。

我们只关心相邻两个位置的大小关系，而两条折线 \(a_i=\min(h_i,2L-h_i),a_{i+1}=\min(h_{i+1},2L-h_{i+1})\) 的交点只有一个，所以相邻数的大小关系将 \(L\) 切分成 \(n\) 个本质不同的段。

算法一： 可以得到平方做法：将小于号看成 \(0\)，大于号看成 \(1\)。我们的目标是对所有左端点 \(l\) 求出最远的右端点 \(f_l\)。每次找到所有 \(01\) 连续段 \([l,r]\)，对所有 \(u\in[l,r]\) 执行 \(f_u\gets \max(f_u,r)\)。

考虑我们每次翻转一个 \(0/1\) 只会影响其周围的 \(\mathcal{O}(1)\) 个连续段，所以修改后对这些连续段单独 chkmax 即可，复杂度 \(\mathcal{O}(n\log n)\)。

有关 \(h_i\neq h_{i+1}\) 的情况，在中间插入 \(\infty\) 并钦定大小关系始终不变即可。

算法二： 可以将条件转化为不存在“谷”，即 \(a_{k-1}\leq a_k\geq a_{k+1}\) 的结构。讨论可以得到一个有关 \(L\) 的范围的限制，判断范围非空即可。利用带删双指针（类似双栈模拟队列）可以做到 \(\mathcal{O}(n)\)。

P10145 [WC/CTS2024] 线段树

难度：7

似乎是复制粘贴，所以大家看原文就好了

考虑怎么判断合法。将原问题抽象成图论问题，一个区间 \([l,r)\) 已知看做 \(l\) 和 \(r\) 连一条双向边，则 \([L,R)\) 能被唯一确定当且仅当 \(L\) 和 \(R\) 联通。证明即考虑已知区间 \([l,r)\) 相当于知道 \(S_r-S_l\) 的值，其中 \(S_x\) 为 \([0,x)\) 的和。这样构建出来的图是平面图，边不会交叉。

设计 DP 状态 \(g(u)\) 表示节点 \(u\) 的左端点和右端点联通，\(f(u,i)\) 表示 \(u\) 的左端点最远能到达的结点为 \(i\)，转移方程：

• \(g(u)\gets 2g(ls)g(rs)\)。
• \(g(u)\gets f(ls,x)g(rs),f(u,x)\gets f(ls,x)g(rs)\)。
• \(g(u)\gets g(ls)f(rs,y),f(u,y)\gets g(ls)f(rs,y)\)。
• \(g(u)\gets f(ls,x)f(rs,y),f(ls,x)\gets f(ls,x)f(rs,y)\)。

第四类转移需要注意 \((x,y]\) 区间内的所有点都不与区间外的点联通，所以所有区间的两个端点要么在 \((x,y]\) 内部，要么都在 \((x,y]\) 外部。换句话来说，包含 \(x,y\) 的区间集相等。xor-hashing 刻画。

那么 \(f(u,i)\) 表示最远点的等价类为 \(i\)，线段树合并维护，复杂度 \(\mathcal{O}(n\log n)\)。

https://www.luogu.com.cn/record/146497898