10.1
gym104922I
模拟赛 T4。
wqs 二分，维护 dp 值和取到 dp 值的 \(k\) 的区间。倒序记录方案，要满足能落到合法区间中。
10.2
模拟赛 T3
建子序列自动机，DAG 上 dp 并按字典序出边贪心记录方案。DAG 链剖分。\(u\) 向 \(2f_v\ge f_u\) 的 \(v\) 连边，形成内向树。重边倍增，轻边跳一次 \(f_u\) 减半。
10.3
模拟赛 T2
拆贡献为跨过 \(i\) 时的答案，枚举有 \(j\) 个 \(\le i\)。
10.5
Q9449
从后往前加，维护拓展域并查集。每次合并后，需要能凑出和为 \(n\)。拓展域限制 \(siz_i,siz_j\) 只能选一个，维护 \(a_i-b_j\)。bitset 二进制分组，本质不同数 \(O(\sqrt n)\) 级别。复杂度 \(O(\frac{\sqrt nn^2}{w})\)。
10.8
模拟赛 T3
\(u\to v\) 等价与 a 中的出现顺序 \(u\to u+1\) 先于 \(u+1\to u+2\)。设 \(dp_{i,j}\) 表示前 \(i\) 个，第 \(i\) 个排名为 \(j\)，前缀和维护。
模拟赛 T4
\(l\) 最远的合法 \(r\) 满足前缀 ( 加 ? 减 ) 大于 \(0\)。限制为 \(g_r\le l\le r\le f_l\)，维护奇偶的区间历史和单点修改线段树扫描线。
10.10
模拟赛 T4
计算已知当前可能为 \(s\) 的答案，每次分裂，只用算 \(k\) 次。将每个起点的状态压为一个数，复杂度 \(O(nmk)\)。
标签：2024.10,le,记录,T4,dp,维护,模拟 From： https://www.cnblogs.com/yhddd/p/18457292