B. Yet Another Subsequence Problem
题意：按照给定方式生成 01 串，求本质不同子序列个数，生成方式可以理解为从 \((0,0)\) 沿折线走到 \((A,B)\)，若在折线上方或在折线上，就往右走（\(0\)），否则往上走（\(1\)）。
套路地设 \(f_{i,0/1}\) 前 \(i\) 个数以 \(0/1\) 结尾的不同子序列个数，显然可以矩乘优化。
然后发现由于是一条直线，那么当 \(\dfrac{B}{A} \ge 1\) 时，每次往右走后都会至少往上走 $\lfloor \dfrac{B}{A} \rfloor $ 次，同理 \(<1\) 时每次往上走后至少会右走 \(\lfloor \dfrac{A-1}{B} \rfloor\) 次，那么考虑类欧实现这个过程，每次把若干个 01111... 缩成新的 0 或把 10000 缩成新的 1 即可。
复杂度 \(\Theta(\log n)\)。
C. Palindrome
题意：给定一个字符串，区间询问有多少种方案删掉最短的区间使得变成回文串。
显然可以从回文中心去考虑，先考虑偶数长度的，奇数同理，不再赘述。设 \(f_i\) 位 \(s[1,i]\) 与 \(s[i+1,n]\) 的反串的 lcs，那么若最后回文中心是 \(i\)，那么 \([i-f_i + 1,i+f_i]\) 都不用删。设 \(cur\) 为 \(s[l,n]\) 与 \(s[1,r]\) 反串的 lcp，那么 \([l,l+cur-1]\) 和 \([r-cur+1,r]\) 是不用删的。
不失一般性地，我们假设最后的回文中心 \(i \le \dfrac{l+r}{2}\)。那么就有 \([i-f_i+1,i+f_i]\) 要与 \([l,l+cur-1]\) 有交，显然 \(i\) 越大越好，因为答案是 \((r-l+1)-2\times(i-l+1)\)，这是个偏序问题，可以直接求出。然后方案数就是 \([l,l+cur-1]\) 和 \([i-f_i+1,i]\) 交大小。
复杂度 \(\Theta(n\log n)\)。
I. Phony
题意：题意：给定 \(n\) 个数，\(k\) 固定，有两类操作：操作 \(1\), 将最大的数减去 \(k\)，重复执行 \(t\) 次；操作 \(2\), 求全局第 \(c\) 大的数值。
把每个数放到数轴上考虑，我们称一个团为一些点的集合满足两两之间距离 \(<k\)，显然这样的团一定是呈周期移动的（从大到小依次移动）。考虑利于 \(k\) 固定的性质直接去模拟这个过程，可以直接维护最大值所在的团，然后每次找到除了这个团之外最大的数，移动这个团直到这个数被缩到这个团为止，可以简单计算移动次数。
实现上有很多细节，比如有可能当前是在移动过程的中间，团中最大的几个移动了，前几个还没移动，此时维护一个 \(cur\) 表示还要多少没移动的，用平衡树维护这个过程即可，实现过程细节很多。
复杂度 \(\Theta(n\log n)\)。
L. Yet Another Maximize Permutation Subarrays
题意：给定一个排列，交换两个位置使用子排列个数最多
显然放到逆排列上去看，就是让前缀的连续段个数尽量多。由于仅交换一次，所以对全局来说没太大的影响。
我们不妨先找到所有合法的前缀，去找到哪些操作会让它们变得不合法，如 \([L,R]\) 的连续段操作一个 \(x \in [L,R]\) 和 \(y > R+1\) 会不合法，还有一些情况，在此不详细展开了，可以描述为矩阵 \(-1\)。
再找到所有操作一次可以合法的前缀，可以分为有两个连续段，或有三个连续段并且有一个长度为 \(1\) 的情况分别考虑，可以用并查集维护连续段即可，也是可以规约到矩阵加 \(1\)。
扫描线求 max 即可，复杂度 \(\Theta(n\log n)\)。
M. Inverted
粗略题意：多次新加点 \(x+n\)，复制节点 \(x\) 的连边，求生成树个数。
设所有有新加点的点是白色的，其他都是黑色点。显然对于每个白色联通块是独立的。
考虑 dp 统计方案，设 \(f_{u,0/1}\) 为 \(u\) 通过自己子树里当前的连边是否可以与 \(u+n\) 联通，设 \(d_u\) 为与 \(u\) 相连的黑点个数。
转移时，设 \(g_v\) 为 \(u\) 不能通过 \(v\) 走到 \(u+n\) 的方案数，那么有 \(g_v = 2 \times f_{v,1}+f_{v,0}\)，表示若 \(v\) 能联通就要断掉 \(u \to v\) 或 \(u + n \to v + n\) 中的一条，否则必须联通。
那么有 \(f_{u,0} = 2^{d_u} \times \prod\limits_v g_v\)，表示 \(u\) 所以连的黑点要么 \(u\) 断要么 \(u+n\) 断，当 \(d_u > 0\) 时，\(f_{u,1}\) 可以通过自身联通，方案是 \(d_u \times 2^{d_u - 1}\)，表示选一个黑点通过它联通，其他断开。除此以外，\(f_{u,1}\) 还有 $\sum\limits_v f_{v,1} \prod\limits_{w \neq v} g_w $，可以通过前缀和优化。
复杂度 \(\Theta(n^2)\)。
H. Quake and Rebuild
题意：给定一棵树, 每个点 \(i(i>1)\) 有一个 \(fa_i (fa_i < i)\) 表示 \(i\) 的父亲。
考虑 P7907 的做法，变成同一个块内多个点一起向上跳，若存在两个点的 \(fa\) 相同，直接暴力跳这个块，显然只会出现 \(\Theta(\sum k)\)，可以用单次 \(\Theta(\sqrt{n})\) 的代价完成，若各不相同就各自直接跳就好了。
复杂度 \(\Theta((n+m+\sum k) \sqrt{n})\)。
标签：Onsite,联通,cur,Qinhuangdao,Cup,复杂度,个数,Theta,题意 From： https://www.cnblogs.com/MiniLong/p/18503140