WC 2024 补题记录

场上打成唐氏了．

A. 代码堵塞

拆贡献到每个位置．考虑计算一个 $a_i$ 会对答案贡献多少次．

对 $i$ 的类型分类讨论：

1. 钦定 $i$ 结果可见时，编号 $< i$ 结果可见的题目会在 $i$ 之前被尝试解决，此时限制为这些题目用时总和不超过 $T - t_i$．统计方案数是一个背包问题，直接做即可．注意编号 $> i$ 的题目状态任意，方案数需乘上 $2^{n - i}$．

2. 钦定 $i$ 结果不可见时，编号 $> i$ 结果可见的题目会在 $i$ 之前被尝试解决，此时限制为这些题目用时总和不超过 $T - \sum_{j \le i} t_j$．这也是背包．

然后就做完了．

* B. 水镜

注意到对于一个区间的翻转状态，可行的 $L$ 会在一个区间内．又打表注意到，对于一个区间的所有翻转状态，可行的 $L$ 的并是一个区间．这玩意我不会证啊，如果你会证欢迎以任何方式联系我或 ckain．

由于拼接两个区间显然只会在接缝处多产生一个限制，故这玩意记录左右端点翻转状态后显然可以合并，然后套上你喜欢的数据结构就能 $O(n \log n)$ 解决了．

还能不能再牛一点？使用 不删双指针 技巧，即可 $O(n)$ 解决．

! C. 线段树

还有机会补吗？