NOIP 2024 题解
T1
首先对于两个串都不能动的位置，直接统计是否相等。
对于连续的一段能动的位置，这一段的数可以随便交换，可以预处理每个位置属于哪一段，以及这一段中 0 和 1 的个数。
我们贪心地考虑，优先匹配一个串能动，另一个串不能动的位置。可以感受到，先把不能动的位置匹配掉后，剩下的位置是两个串都可以随便移动的，剩下的位置限制会更松，于是这样是比较优的。
最后处理都能动的位置，我们贪心地能匹配就匹配，因为匹配和失配的贡献都是 1，所以与匹配的顺序无关。
时间复杂度 \(O(Tn)\)。
T2
按照确定的点分段，考虑到每一段都是独立的。
考虑求每一段合法的方案数，正难则反，用总数减去不合法的方案数。
不合法的方案数就是设左边值为 \(x\)，右边为 \(y\)，构造一种条件形如当左边为 \(x\) 时右边不为 \(y\)。
这就要求这一段前后连起来，且最后一个值不为 \(y\)，大概就是：
\[V^{len}\times (V-1) \]再考虑开头的和结尾的两段，发现怎么取都是合法的。
我们需要快速幂，时间复杂度 \(O(Tm\log n)\)。
T3
T4
\(O(Qn\log ^2n)\sim O(Qn\log n)\)
考虑枚举长为 \(k\) 的段，求 LCA。
一段的 LCA 就是每次加一个点求 LCA，也可以是合并两个子区间的 LCA。
可以考虑线段树上合并区间 LCA，每次合并用倍增实现 \(O(\log n)\)，也可以在欧拉序上 \(O(1)\) 求 LCA。
\(O(Qn+n\log ^2n)\sim O(Qn+n\log n)\)
可以用 ST 表代替线段树，预处理 ST 表合并时可以倍增 \(O(\log n)\) 也可以 \(O(1)\) 求 LCA。
另外，也可以求区间欧拉序的最小最大值，类似欧拉序两个点的 LCA，求 RMQ，这样也能做到 \(O(nQ+n\log n)\)。
性质 B
上面的做法可以直接通过性质 B。
性质 A
考虑整体二分，就要实现一个数据结构，支持加入或删除一个点，然后查询区间内最长连续段的长度是否大于等于 \(K\)。
可以用线段树实现，时间复杂度 \(O((Q+n)\log ^2n)\)。
\(O((Q+n)\log^2 n)\)
如果有强大的观察能力或联想能力，可以发现一段区间的 LCA 的深度就是相邻两个点的 LCA 深度的最小值，即
\[\min\{\text{dep}_{\text{LCA}(i,i+1)}\} \]证明就是，考虑这一段区间的 LCA，这段区间的点分布在 LCA 的不同子树内，则一定有 \(i,i+1\) 跨在不同子树内。
于是就转化为了性质 A。
\(O((Q+n)\log n)\)
考虑对于每个点 \(i\)，设 \(s_i=\text{dep}_{\text{LCA}(i,i+1)}\)，求出 \(\min_{l_i\le j\le r_i}\{s_j\}=s_i\) 的极大区间 \((l_i,r_i,s_i)\)。
设询问区间为 \((L,R)\)，就是求 \((l_r,r_i,s_i)\) 与 \((L,R)\) 的交大于等于 \(K\) 的区间的最大 \(s_i\)。
分类讨论，当 \(r_i\le R\) 时，要满足
\[L+K-1\le r_i\le R \land r_i-l_i+1\ge K \]当 \(r_i\ge R\) 时，要满足
\[l_i\le R-K+1\land r_i\ge R \]前者对 \(r_i-l_i+1,K\) 扫描线，后者对 \(r_i,R\) 扫描线。
具体地，把做扫描线的量排序，然后双指针把另一个量加入数据结构中或在数据结构中查询。
前者 \(L+K-1\le r_i\le R\) 可以线段树，后者 \(l_i\le R-K\) 可以树状数组。
当 \(K=1\) 时，需要特殊处理，直接用数据结构查区间最值。可选 ST 表。
时间复杂度 \(O((Q+n)\log n)\)。
标签：le,log,NOIP,题解,可以,一段,2024,LCA,区间 From： https://www.cnblogs.com/dccy/p/18592686