Day13(20241112)
获得成就：在集训队员中登顶。
T1 线段树与区间加
感觉题解做法很牛，所以我来写一下我的 \(O(n\log n+q\sqrt{n})\) 做法。
我们先考虑单独维护 \(laz\) 数组。
如果先不考虑 pushdown。发现我们对区间 \([l,r]\) 进行加法操作，就是找到所有 \([L_i,R_i]\subseteq[l,r]\) 且 \([L_{fa_i},R_{fa_i}]\subseteq[l,r]\) 的节点 \(laz\) 增加 \(k\)。发现这个限制太奇怪了，所以我们考虑对于所有 \([L_i,R_i]\subseteq[l,r]\) 的节点 \(laz\) 增加 \(k\)。那么一个节点实际上的 \(laz_i\) 就等于 \(laz_i-laz_{fa_i}\)。
那么对其求和就有 \(\sum vb_i(laz_i-laz_{fa_i})\)，交换一下顺序就有 \(\sum laz_i(vb_i-vb_{ls}-vb_{rs})\)。发现这样 pushdown 只需要把那些要 pushdown 的节点的 \(laZ_i\) 变成 \(0\) 即可。
我们记 \(val_i=vb_i-vb_{ls}-vb_{rs}\)，那么我们维护的操作有：
- 对于所有 \([L_i,R_i]\subseteq [l,r]\) 的节点 \(laz_i\) 加上 \(k\)。
- 对于所有 \([l,r] \subseteq[L_i,R_i]\) 且 \([L_i,R_i]\not\subseteq [l,r]\) 的节点的 \(laz_i\) 清空。
- 查询的 \(\sum val_ilaz_i\)
发现把所有的 \((L_i,R_i)\) 看成二维平面上的点，那么要做的操作就是矩形加和矩形推平，考虑使用 KDT，时间复杂度为 \(O(q\sqrt{n})\)。
现在再考虑吧 \(a\) 数组。
仍然沿用上面对于 \(laz\) 的修改，那么对于一个区间，如果这个区间的实际区间和为 \(sum_i\)，那么有 \(a_i=sum_i-laz_{fa_i}*len_i\)。
那么维护 \(\sum va_ia_i\) 就是要维护 \(\sum va_isum_i-\sum laz_i(va_{ls}len_{ls}+va_{rs}len_{rs})\)。对于前者，每一次修改的贡献可以通过前缀和和差分实现；对于后者，只需要将 \(val_i\) 修改成 \(vb_i-vb_{ls}-vb_{rs}-va_{ls}len_{ls}-va_{rs}len_{rs}\) 即可。时间复杂度仍然是 \(O(n\log n+q\sqrt{n})\)，感觉跑起来还挺快的。
T2 字符串
考虑 \(S[i,i+l-1]<S[i+l,i+2l-1]\) 意味着什么，发现在绝大多数情况下等价于 \(rk_i<rk_{i+l}\)，其中 \(rk_i\) 表示 \(i\) 在后缀数组中的排名。
而 \(rk_i<rk_{i+l}\) 可以直接二维数点，使用树状数组可以做到 \(O((n+q)\log n)\)。
发现反例就是 \(S[i,i+l-1]=S[i+l,i+2l-1]\) 但 \(rk_i<rk_{i+l}\) 的情况。考虑如何处理 \(S[i,i+l-1]=S[i+l,i+2l-1]\)。
直接使用优秀的拆分的 trick，先枚举 \(l\)，然后找到满足 \(S[i,i+l-1]=S[i+l,i+2l-1]\) 的 \(i\) 连续段 \([L,R]\)，那么如果有 \(rk_L<rk_{L+l}\)，那么这一段区间都是被额外统计的。而这样的连续段最多只有 \(O(n\log n)\) 段，仍然使用树状数组进行二维数点可以做到 \(O((n+q)\log^2n)\)，常数较小可以通过。
发现这种结构其实就是 runs，所以我们对于每一个 runs，枚举最小循环节重复多少次，这样得到的连续段 \([L,R]\) 只有 \(O(n)\) 个，时间复杂度也就做到了 \(O(n\log n)\)。
T3 格雷码
据说可以把这个题的大致做法。
发现格雷码的限制比较宽松，所以认为在 \(n\mid 2^n\) 时，极差为 \(0\)；\(n\not\mid 2^n\) 时，极差为 \(2\)。
你发现直接构造是不太可能的，所以考虑增量构造。发现 \(n\to n+1\) 不太现实，所以考虑 \(n\to n+2\)。
在 \(n+2\) 中，我们对于后 \(n\) 位的构造还是依赖 \(n\) 的结果，想办法对于前两位来进行构造。
我们将 \(n\) 的序列拆成：\(A_1P_2A_2P_2\dots A_mP_m\)，其中 \(A_i\) 是一段操作，\(P_i\) 是单个操作，\(A_i^R\) 记为 \(A_i\) 反转后的结果。
题解给出如下构造方式（\(m\) 为奇数）：
\[\begin{matrix}A_1,n+1,A_1^R,n+2,A_1,P_1\\A_2,n+2,A_2^R,n+1,A_2,P_2\\\dots \\A_m,n+1,A_m^R,n+2,A_m\\n+1,A_m^R,P_{m-1},\dots A_2^R,P_2,A_1^R,P_1,n+2\end{matrix} \]发现 \(A\) 中的数出现了 \(4\) 次，\(P\) 出现了 \(2\) 次，但 \(P_m\) 没有出现，\(n\) 和 \(n+1\) 出现了 \(m+1\) 次。由于极差取的是最小值，所以数字出现次数的集合是确定的，想办法找到一组满足条件的分割即可。
标签：vb,rs,sum,W5,ls,laz,IOI2025,subseteq,互测 From： https://www.cnblogs.com/Xun-Xiaoyao/p/18541840