NOI2023 题解

打的太 shaber 了，于是补补题。

D1T1

扫描线。
首先我们可以容斥一下，答案为被一种操作覆盖到的减去被两种操作覆盖到的加上被三种操作覆盖到的。
首先考虑只被一种操作覆盖到的，这很简单，直接上个区间颜色段推平就好了，顺便去了个重。
接下来是有被斜线覆盖到的，这样的点数为 \(O(nk)\)，直接枚举暴力存点即可，用 std::map 记下来即可。
比较有难度的是横纵计数，考虑扫描线，那么相当于每次是一个单点修改和区间查询，树状数组即可。
时间复杂度 \(\Theta(n\log n)\)

D1T2

找规律。
首先我们考虑 \(k=0\) 这档怎么做。
先考虑 \(k=0,n=1\)，此时每次加入一个点，要么认一个父亲，要么插入在一条边中。
答案为 \(\prod_{i=1}^m 2i-1\)。
拓展一下，发现如果有 \(n\) 个点，相当于在一开始就多了 \(2n-2\) 种选择(去掉了认 \(1\) 为父亲的那种)。答案为 \(\prod_{i=1}^m 2n+2i-3\)。
现在考虑 \(k>0\) 应该怎么做，我们发现每次我们可以考虑从一条边中拉一个点出来。相当于原来有一条 \(x \to y\) 的边，现在要变成 \(x \to z \to y\) 同时 \(z \to w\)。我们先将 \(z\) 空着放到之后填，但是 \(z \le k+w\)，所以我们考虑将要填掉的 \(z\) 压起来。
设 \(dp_{i,s}\) 表示填到 \(n+i\)，前 \(k\) 个点的状态是 \(s\)，得到转移方程。
有三种转移：

像 \(k=0\) 那样转移，转移系数为 \(2(n+i+pc(s))-1\)。
拉出一个点，那么状态要与上一个 \(1\)，系数为 \(1\)。
选择一个点，考虑消除填掉这个点对应的 \(z\)，那么状态要异或上一个数，系数为 \(1\)。

特别地，最高位为 \(1\) 时强制转移第三种，且选择的点也是固定的。
答案为 \(dp_{m,0}\)，时间复杂度 \(\Theta(m 2^kk)\)。

D1T3

首先观察到一个树是 dfs 树，当且仅当所有额外边是返祖边。
那么可以容斥

\[\sum_{T \subseteq S,T \ne \varnothing} (-1)^{|T|-1} 2^{合法边数} \]

那么现在要考虑对于 \(T\) 中每个点都合法的边数了。
考虑特殊性质 \(B\) 应该怎么做，此时只有返祖边。
一条额外边满足条件当且仅当他被虚数上的一条边包含，或者虚数边上的一个点指向不在虚树中出现的子树。
记 \(f_{u}\) 表示以 \(u\) 为根的子树中 \(u\) 被钦定在虚树中的方案数，那么转移过程形如一个背包。
一个点出现在虚树有两种情况：

存在至少两个不同的子树中有关键点，那么这个点选不选无所谓。
小于两个子树中有关键点，那么这个点必须被选择。

但是注意到，转移的时候选择 \(f_v\)，实际上转移过来的值为 \(f_v \times 2^{u,v 路径的合法值}\)，于是考率维护实际的转移值 \(g_v\)。
对于第一类边 \(u \to x\)，转移为对 \(x\) 的整棵子树乘 \(2\)。
对于第二类边，我们要处理对于每个 \(u\) 处理出 \(fa_u\) 到 \(u\) 这一方向上所有的额外边 \(A_u\)，那么此时的更新为，对于 \(u\) 的一个儿子 \(v\)，将不是 \(v\) 的子树都乘上 \(A_u\)。
背包的过程中，一棵子树既可以选择子树中某点的 \(g\) 值，也可以选择不选关键点，乘上 \(2^{A_v}\) 转移。
最后在 \(u\) 处统计答案，贡献为 \(f_u\) 乘 \(u\) 向 \(fa_u\) 方向的所有点是否选的方案数。
发现对 \(g\) 的操作全是区间乘法，区间求和，可以用线段树维护。

现在我们有横叉边。对于 \(u\) 的维护是没有区别的，问题出在在横叉边 \((u,v)\) 的 LCA 处统计答案时，如果只有 \(u\) 子树和 \(v\) 子树中选择点，那么此时可以选择这条边。
这是一个一个矩形乘，矩形差的形式，要统计子树中恰选两个的方案数，这个过程可以直接扫描线维护，相当于一个矩形面积并。
时间复杂度 \(\Theta((n+m)\log n)\)。

D2T1

首先发现树高很小，那么每个点暴力跳 \(fa\) 复杂度是对的。
将每次上去一段，再跳回子树，再上去一段的操作看作一条向下的边。由于再次上去的操作不会超过第一次上去的位置（这样成环了），所以转换可行。
统计出每个点到左右子树的最短路，那么一个点对答案的贡献到自己子树和加上该点到某祖先另外一个子树的贡献。
至于预处理最短路，可以做一个简单 dp，然后考虑每个点对祖先的贡献。
时间复杂度 \(\Theta((2^n+m)n^2)\)

D2T2

首先有一种 bitset 的暴力做法是小常数 \(O({n^2 \over \omega})\)，可以直接通过，这里就不讲了。
首先，一个方案合法就是前缀的字典序小于后缀的。
这样我们可以对原串和反串的做后缀排序，然后归并起来，这样位置 \(j\) 对于一个询问 \((i,len)\) 合法，当且仅当 \(rk_i<rk_j\) 且 \(i \le j \le i+2len-1\)。
这是一个二维数点，可以直接离线树状数组。
但是还是有情况不合法，就是回文串。
怎么样的回文串是会被统计的呢？对于一个回文串 \(S[l:r]\)，他会被统计到当且仅当 \(S[l-1]>S[r+1]\)。这样的回文串是 \(O(n)\) 的，他会对 \(l \le i \le mid\) 的 \(i\) 且 \(i\) 对应的 \(len\) 可以覆盖到的询问产生影响，也是一个数点的形式，扫描线即可。
复杂度为 \(\Theta((n+q) \log n)\)，代码中用哈希维护了一些东西。

D2T3