2025 XYD Summer Camp 8.1 模考
时间线
- 8:30 开题，第一题怎么是集合幂级数，T2 好像很莫队，T3 题目好长，决定顺序做题。
- 嘎嘎推容斥式子，甚至推出两层容斥，最后推出一个 $O(4^n)$ 好像没什么前途的式子，精神崩溃，怀疑自己要保龄。
- 于是就先去做了 T2，发现 $n\le 10^5$ 和区间没有包含关系是好做的，前者 $O(n\sqrt n\log n)$ 后者双指针，写完就有 70pts 了，再回去继续推 T1 式子。
- 回来决定重新推，发现把其中一层容斥换成一个 $O(3^n)$ 暴力枚举就好了（一开始还想了一个 dp 加速容斥式子，原因是赛前在写小星星）。
- 等到样例过了是 11:00，决定去冲一下 T3 拿拿部分分。
- 哇好多部分分，好像有一个比较显然的 $O(nk)$ dp，写写写发现过不了大样例，以为 dp 是错的（实际是因为大样例 $n,k$ 太大了，当时没看清），精神崩溃，想着交上去骗分也好。
- 最后 15 min 的时候发现 T1 复杂度是 $O(n3^n)$！把暴搜从循环里拿出来提前处理就变成 $O(3^n+n)$ 了，非常可怕。
- 笑点解析：以为自己的 177 是 100+70+7，实则 T3 反向挂分、T2 正向挂分。
分数
$100+30+47=177$。
题解 & 错因
T1
给定 $n$ 个人和 $m$ 个工作，第 $i$ 个人有 $0\sim 2$ 个讨厌的工作，求每个人选一个工作、一个工作最多被一个人做，且没有人做自己讨厌的工作的方案数。
$n\le 17$，$m\le 10^6$。
考虑令 $g(S)$ 表示 $S$ 中的人都做讨厌的工作、$S$ 外的人都做喜欢的工作的方案数，转部分满足，设 $f(S)$ 表示 $S$ 中的人一定做讨厌的工作的方案数，其余人随意。设 $h(S)$ 表示 $S$ 中的人做讨厌的工作的情况下，对这 $S$ 个人分配工作的方案数，那么有 $$ f(S)=h(S)(m-|S|)^{\underline{n-|S|}} $$ 因为 $$ f(S)=\sum_{T\subseteq S}g(T) $$ 所以 $$ g(S)=\sum_{T\subseteq S}(-1)^{|T|-|S|}f(T) $$ 答案显然是 $g(\varnothing)$，于是 $$ \begin{aligned}g(\varnothing)&=\sum_{T}(-1)^{|T|}h(T)(m-|T|)^{\underline{n-|T|}}\&=\sum_{i=0}^n(-1)^i(m-i)^{\underline{n-i}}\sum_{|T|=i}h(T)\end{aligned} $$ 这个时候就不要往下推了！注意到 $h(T)$ 这个东西可以直接暴搜枚举每个人做不做讨厌的事情、做哪件讨厌的事情，假设某次暴搜出一个大小为 $siz$ 的合法情况，直接贡献到 $\sum_{|T|=siz}h(T)$ 里即可。时间复杂度 $O(3^n+n)$。
T2
给定一个长度为 $n$ 的序列 $a$，$Q$ 次询问每次给定一个区间 $[l,r]$，求将 $a$ 中 $[l,r]$ 的部分从小到大排序后，区间中相邻元素原本在 $a$ 中的编号的差的绝对值之和。不强制在线。
$n,Q\le 5\times 10^5$，$a$ 中元素两两不同，时限 8s。
考虑莫队，一个比较直接的想法是用平衡树维护当前区间内元素排序后的结构，增删贡献是简单的，时间复杂度 $O(n\log n\sqrt n)$。如果不考虑添加元素，只有删除，那么可以用一个双向链表来快速查询一个被删除的元素的前驱后继，所以把莫队换成回滚莫队即可。时间复杂度 $O(n\sqrt n)$。
- 填一下回滚莫队的坑：考虑把普通莫队的删除操作改成加入后撤销，将所有询问按照左端点所在块从小到大、右端点从小到大排序，那么对于所有左端点在同一块的询问，右端点单调递增；设当前询问区间是 $[ql,qr]$，莫队的区间是 $[l,r]$，策略就是：总是令 $l$ 在 $ql$ 所在的块的右端点，先将 $r$ 移到 $qr$（只有增加），再将 $l$ 移到 $ql$，再将 $l$ 撤回到 $ql$ 的块的右端点。这可以通过记录一个栈表示最新的操作更改了哪些位置，原本这些位置的值是什么。
- 如果 $ql$ 所在的块变化了，那么更新 $l$ 到新的块的右端点，将莫队清空。回滚莫队的时间复杂度依然是 $O(n\sqrt n)$。对于这题只能删除的莫队，可以考虑把左端点在同一个块的区间的右端点降序，一开始在莫队里插入 $1\sim n$ 所有元素，左端点总是放到一个块的左端点上；那么每轮询问就是：删若干次右端点，删若干次左端点，撤回删的左端点。
- 当块变了的时候可以直接从$1\sim n$ 删左端点删成一个初始状态。
- 当询问在同一个块里的时候，我想的做法是预处理每个块排序后的结果，每次提出这个块询问区间的子序列，直接算答案，时间复杂度 $O(\sqrt n)$。
不知道暴力莫队哪个地方写错了，导致好像复杂度有些问题，可能是 set 访问地址的问题？
T3
给定一棵 $n$ 个点树，第 $i$ 个点有两个参数 $(t_i,w_i)$；你需要给每条边 $(u,v)$ 定一个边权 $w(u,v)$，然后对于每个点 $u$，如果 $u$ 到根的路径中的边权最小值恰好等于 $t_u$ 那么你可以获得 $w_u$ 的收益。求最大收益。
$n\le 10^6$。
考虑树形 dp，令 $f(u,t)$ 表示 $u$ 与其父亲的边边权设为 $t$ 得到的答案。那么有转移： $$ f(u,t)=[t=t_u]w_u+\sum_{v\in\mathrm{son}u}\max{t’\le t}f(v,t’) $$ 令 $g(v,t)=\max_{t’\le t}f(v,t)$ 即每个点的 dp 数组的前缀 $\max$，那么转移变成 $$ f(u,t)=[t=t_u]w_u+\sum_{v\in\mathrm{son}_u}g(v,t) $$ 可以发现这相当于先将子树的 $g$ 数组相加，然后再做一个单点加，最后求一遍前缀 $\max$ 得到 $g(u,t)$。考虑每一个本质不同的前缀 $\max$ 其实只对应一个 $t_u$ 的位置，因此可以考虑线段树合并。
- 首先，用线段树维护每个点 $g$ 的区间 $\max$、区间第一个数以及区间最后一个数的值。
- 考虑合并两个线段树节点 $l,r$，如果 $l,r$ 中有一个节点中整个区间都是区间 $\max$，此时就可以看成在另一个线段树节点上执行区间加这个节点的区间 $\max$，打一个区间加懒标记即可。
- 现在我们递归得到了合并完成的节点 $rt$ 的左右儿子节点 $l,r$，直接合并进 $rt$ 中即可。
可以发现若干个单调不降的数组加起来结果仍然单调不降，因此我们只需考虑在 $t_u$ 上加上 $w_u$ 对 $g$ 的影响。这相当于一个区间推平，右端点是第一个大于 $w_u+f(u,t_u)$ 的位置。线段树二分即可。
这么构式的方法还真让我过了