\(\text{By DaiRuiChen007}\)
D1T1. 水镜
给定 \(a_1\sim a_n\)，求多少个 \([l,r]\) 满足存在实数 \(L\)，将若干个 \(a_i\) 变成 \(2L-a_i\) 后 \(a_l\sim a_r\) 严格递增。
数据范围：\(n\le 10^6\)。
考虑钦定 \(i-1\) 翻转 / 不翻转，\(i\) 翻转 / 不翻转，容易发现只有 \(a_{i-1},a_i,L\) 满足某些条件时某些状态才能成立。
那么不合法一定是 \(i-1\) 无论怎么选，\(i\) 都必须翻转 / 不翻转，且 \(i+1\) 无论怎么选，\(i\) 都必须不翻转 / 翻转，这样就导出矛盾了。
如果不存在矛盾，那么总能构造出一组解，因此手玩得到充要条件为：
- \(a_i\ge\max(a_{i-1},a_{i+1})\) 时，\(2L>a_i+\min(a_{i-1},a_{i+1})\)。
- \(a_i\le \min(a_{i-1},a_{i+1})\) 时，\(2L<a_i+\max(a_{i-1},a_{i+1})\)。
ST 表维护对 \(2L\) 的区间限制，对每个左端点二分最大合法右端点即可。
时间复杂度 \(\mathcal O(n\log n)\)。
D1T2. 线段树
给定长度为 \(n\) 的序列上一棵不均匀的线段树，以及 \(q\) 个查询区间，求有多少个线段树上的节点集合，使得直到这些节点对应的区间和后，能确定每个查询区间的区间和。
数据范围：\(n,m\le 2\times 10^5\)。
对 \(1\sim n\) 的每个位置被查询区间的覆盖情况划分等价类，那么我们必须分别确定每个等价类内部的元素和。
考虑什么样的节点集合是好的，我们把这些节点对应的区间划分也等价类，他们是好的当且仅当同一等价类的任意节点在上一步内也在同一等价类中。
那这就相当于把所有被选中的节点 \(u\) 在线段树和 \(fa(u)\) 把边断开，要求不同等价类的元素不连通，且要么没有和根节点联通的等价类，要么该等价类不被任何查询区间覆盖的等价类。
那么可以树形 dp，\(dp_{u,i}\) 表示 \(u\) 子树内只有等价类 \(i\) 和 \(u\) 联通的方案数，设 \(u\) 的线段树左右儿子为 \(l,r\)，转移如下：
\[\begin{aligned} dp_{u,i}&=dp_{l,i}\times dp_{r,0}+dp_{l,0}\times dp_{r,i}+dp_{l,i}\times dp_{r,i}\\ dp_{u,0}&=2\times dp_{l,0}\times dp_{r,0}+\sum_{i>0} dp_{u,i} \end{aligned} \]\(dp_{u,0}\) 的转移是考虑 \(u\to fa(u)\) 可不可以不断开。
转移时考虑 std::unordered_map 启发式合并，维护 \(\sum_{i>0}dp_{u,i}\) 并特殊计算 \(dp_{u,0}\)，剩余的修改相当于全局乘和单点加，容易解决。
注意特判轻儿子的 \(dp_{v,0}\) 恰好为 \(\bmod P=0\) 的情况。
时间复杂度 \(\mathcal O(n\log n)\)。
D1T3. 众生之门
给定一棵 \(n\) 个点的树，求一个 \(n\) 阶排列 \(x\) 使得 \(x_1=s,x_n=t\) 且 \(\oplus_{i=1}^{n-1} \mathrm{dis}(x_i,x_{i+1})\) 最小。
数据范围：\(n\le 5\times 10^4\)。
观察发现我们总存在一个 \(n\) 阶排列 \(x\) 使得所有 \(\mathrm{dis}(x_i,x_{i+1})\le 3\)，因此答案在 \([0,3]\) 之间。
显然答案的奇偶性是一定的，因此我们只要确定答案 \(<2\) 还是 \(\ge 2\)。
打表发现对于绝大部分的树，答案总是 \(0\) 或 \(1\)。
我们可以随机构造，每次随机一组 \(x\)，判断答案是否合法。
我们可以把一组 \(x\) 的权值看成 \([0,n]\) 间均匀生成的随机数，那么期望随机 \(\mathcal O(n)\) 轮就能找到答案。
时间复杂度：\(\mathcal O(n)\)。
D2T1. 多方计算
给定 \(n+1\) 个人编号 \(0\sim n\)，初始 \(0\sim n-1\) 分别知道一个 \([0,2^m)\) 内的正整数 \(a_0\sim a_{n-1}\)。
你可以进行 \(T\) 轮操作，每轮操作所有 \(i\) 同时向某个 \(i+1\) 发送 \(1\) bit 的信息，要求最终 \(n\) 知道 \(\sum a_i\)。
要求 \(T\le n+m+3\)。
数据范围：\(n,m\le 2000\)。
考虑暴力，第 \(k\) 轮第 \(i\) 个人发送 \(\sum_{j=0}^i a_j\) 的的第 \(k-i\) 位，由于产生了 \(\mathcal O(\log n)\) 个进位，因此需要 \(n+m+\log_2n\) 轮发送完成。
考虑优化，注意到 \(k-i<0\) 时不会发送任何信息，可以考虑利用这些冗余操作。
如果 \(k-i<0\)，我们发送第 \(k-i+m+\log n\) 位，那么这一部分的加法会将 \(i>\log n\) 的每个 \(a_i\) 的最高位贡献提前计算，最终发送完成只要 \(n+m+\log\log n\) 轮。
但此时只能做到 \(T=n+m+4\)，考虑如何优化，类似的办法，再提取出一小部分较高位再进行一次加法即可。
D2T2. 投票游戏
给定一棵 \(fa(i)<i\) 的有根树，每个点 \(u\) 对自己的权值有 \(a_u\) 贡献，对自己父亲的权值有 \(b_u\) 贡献。
定义一轮游戏表示不断删除权值最大且未被删除的节点（多个则选取标号最大的节点）并删除之。
\(q\) 次操作单点改 \(a_u,b_u\)，查询进行一轮虚拟游戏后 \(x,y\) 谁先被删除。
数据范围：\(n,q\le 2\times 10^5\)。
显然不可能每次询问都进行一轮虚拟游戏，考虑用一些方式刻画删除顺序。
容易发现每次删除节点后，其他点的权值单调不降，因此我们求出每个点 \(u\) 被删除时对应的权值 \(f_u\).
那么 \(x\) 比 \(y\) 先删除当且仅当 \(f_x>f_y\) 或 \(f_x=f_y\) 且 \(x>y\)。
我们考虑如何暴力求出所有 \(f_u\)，容易发现 \(f_u\) 可以要通过所有儿子的 \(f_v\) 推出。
维护当前的 \(u\) 的权值 \(f_u\)，初始为 \(a_u+\sum b_v\)，把 \(f_v\) 降序排列，即每次取出最先被删除的儿子 \(x\):
- 如果 \(f_u\le f_x\)，因为 \(u<x\) 因此 \(x\) 比 \(u\) 先删除，那么 \(f_u\gets f_u-b_x\)，递归考虑下一个被删除的儿子。
- 如果 \(f_u>f_x\)，那么 \(u\) 比 \(x\) 先删除，\(f_u\) 就是所求答案，结束。
设 \(s_i\) 表示 \(f_v\) 前 \(i\) 大的 \(v\) 对应的 \(b_v\) 之和，\(v(i)\) 表示 \(f_v\) 第 \(i\) 大的 \(v\)。
我们就是要找到第一个 \(a_u+\sum b_v-s_{i-1}>f_{v(i)}\)，即 \(a_u+\sum b_v>s_{i-1}+f_{v(i)}\)。
此时 \(f_u=a_u+\sum b_v-s_{i-1}\)。
可以用一棵平衡树维护每个点的所有儿子，按 \(f_v\) 排序后，求出前缀 \(s_{i-1}+f_{v(i)}\) 的最小值即可在平衡树上二分。
此时单点修改的复杂度难以接受，考虑能不能用 ddp 类似的方法优化。
观察 \(f_u\) 和其重儿子 \(x\) 的 \(f_x\) 的关系，不妨设在所有轻儿子中二分求出的答案为 \(w\)：
- 如果 \(w>f_x\)，那么 \(x\) 一定比 \(u\) 晚删除，\(f_u=w\)。
- 否则 \(x\) 一定比 \(u\) 早删除，在所有轻儿子构成的平衡树中二分 \(a_u+\sum b_{v}-b_x\)，得到的答案即为 \(f_u\)。
因此 \(f_u\) 可以表示成关于 \(f_x\) 的分段常函数，很容易合并相邻的两个信息。
并且我们也只要维护每个点轻儿子构成的平衡树。
那么可以直接树剖维护重链信息乘积，更新时修改每条重链链顶父亲的平衡树并更新信息即可。
时间复杂度 \(\mathcal O(n\log n+q\log^2n)\)。
D2T3. 字符串游戏
给定长度为 \(n\) 的字符串 \(S\)，两个人轮流操作，每次删除 \(S\) 的一个前缀 \(T\)，获得的分数等于 \(T\) 在 \(S\) 中的出现次数。
两人都要最大化和对手的分差，求最终先手分数减后手分数的值。
数据范围：\(n\le 10^6\)。
翻转 \(S\) 变成删后缀的问题，记 \(w(l,r)\) 表示 \(S[l,r]\) 在 \(S[1,r]\) 中的出现次数。
维护 \(w(l,r)\) 等于 \(S[l,r]\) 在后缀自动机 Parent-Tree 上对应的节点的子树中有多少 \(\le r\) 的 Endpos。
对 \(r\) 离线后相当于单点加，查询子树和，树状数组维护即可，定位到 \(S[l,r]\) 对应节点可以在 Parent-Tree 上根据长度倍增。
设 \(f_i\) 表示 \(S[1,i]\) 答案，转移为 \(f_i=\max_{j=0}^{i-1} \{w(j+1,i)-f_j\}\) 然后考虑如何优化。
首先我们知道 \(k<j\) 时 \(w(k,i)\le w(j,i)\)，因此如果 \(f_k\ge f_j\) 那么决策 \(k\) 显然不如决策 \(j\)。
那么合法的转移点构成 \(f\) 递减的单调栈，但这依然不足以通过此题。
我们不妨假设 \(i\) 的最优转移是单调栈中某个的 \(j\)，且这个 \(j\) 满足 \(f_j<f_i\)，如果 \(f_j\ge f_i\)，那么 \(j\) 一定被弹出，这个过程带来的转移是均摊 \(\mathcal O(n)\) 的。
我们注意到对于 \(j<k\)，\(w(i,j)\ge w(i,k)\) 因为每次 \(S[i,k]\) 出现，一定能在其前缀中找到 \(S[i,j]\)。
对于单调栈中某个 \(j<k\) 且 \(f_j<f_k<f_i\) 的节点 \(k\)，都有 \(f_i>f_k\ge w(j+1,k)-f_j\ge w(j+1,i)-f_j\)，故这样的 \(k\) 不存在，即 \(j\) 是此时栈顶。
因此 \(f_i\) 只可能从被弹出元素或者弹栈后的栈顶转移，不断用栈顶更新 \(f_i\) 直到 \(f_i\) 大于当前栈顶的 \(f\) 即可。
转移次数和弹栈次数成线性。
时间复杂度 \(\mathcal O(n|\Sigma|+n\log n)\)。
标签：le,log,题解,sum,Link,CTS2024,节点,dp From： https://www.cnblogs.com/DaiRuiChen007/p/18410193