20240703 DS round
T1
考虑区间子区间问题直接扫描线加历史版本和， 考虑修改。
现在扫到 \(r\)， 线段树每个位置 \(i\) 维护的是 \(i\) 到 \(r\) 的区间 \(lca\)，这些 \(lca\) 的深度具有单调性， 考虑直接二分一下位置， 然后 \(r\) 扫到 \(r + 1\) 时， 深度大于 \(lca(r, r + 1)\) 的 \(lca\) 全部覆盖为 \(lca(r, r + 1)\)， 就解决了。
T2
考虑对于时间线段树分治， 然后考虑连通块的神秘式子， 如果 \(x\) 是 \(u\) 的倍数， 那么最后的式子 \(x^v\) 或者指数以上的项， 肯定为 0， 考虑 \(v\) 很小， 我们只需要维护 \(v - 1\) 项， 所以做一下卷积直接 \(O(v^2)\)。 考虑不是倍数的情况， 非常的神秘， 我们有 \(x \equiv r \ mod u\)， 我们可以维护 \(\prod (a_i + r + x - r)\)， 这个时候 \(（x - r）^v\) 或指数大于 \(v\) 的项就为0， 考虑 \(u\) 也很小， 我们对于每个同余类都维护一下即可。
T3
这题考验对 dij 和 floyd 的理解和， 考虑设DP状态 \(f(i, j)\) 为 \(i\) 到 \(j\) 的括号匹配序列的最短路， 考虑括号匹配序列有两种组合， \(AB\)， 和 \((A)\)， 转移也这么走即可， 然后最短的话我们考虑用 dij 转移， 把这么些状态当成 \(n^2\) 个点。
标签：dij,考试题,lca,考虑,维护,式子 From： https://www.cnblogs.com/qerrj/p/18282575