2024.10.3：
能够感受到出题人深深的恶意，扔了道 zak 没场切的交互，甚至 2e5 的输出关同步流被卡了。
A：
一共只有 $ 25 n $ 种本质不同的操作，不妨求出每种操作后的新串的平方子串个数，最后取其中最大值即可。 跨过它们的平方子串（包括修改后新生成的）的贡献。
记 $ L=\min (L C S(a, b) ，len ), R=\min (L C P(a+1, b+1) ，len -1 ) $ ，贡献为 $ \max (0, L+R-k+1) $ 。
至于有修改的情况，不妨先考虑每种修改对 $ L, R $ 分别造成了什么影响。下以 $ R $ 为例说明，设修改了第 $ i $ 个点：
$ i \in[1, a]: R $ 保持不变；
$ i \in[a+1, a+R], R $ 变为 $ i-(a+1) $ 。
$ i=a+R+1 $ ：若将 $ s_{a+R+1} $ 修改为 $ s_{b+R+1} ， R $ 变为 $ R+1+L C P(a+R+2, b+R+2) $ ；否则，仍为 $ R $ 。
$ \max (0, L+R-k+1) $ 取哪一边，可以得到更细致的分类，每一类中的贡献都是一个关于 $ i $ 的一次函数。
于是只要对贡献数组做 $ O(1) $ 次区间加一次函数即可，差分即可。
B：
官解：
考虑三角剖分的对偶图 (去掉外部无限大的面对应的那个点) ，可以发现该对偶图构成一棵树。
并且，若以原图中边 $ (1, n) $ 所在的三角形为树的根，则其是一棵有根二叉树。
我们不妨将其视为一棵二叉搜索树。
在此建模中，可以发现，题面中的一次操作对二叉树形态的影响，相当于二叉树中的一次左旋/右旋操作。
同时，注意到点 $ x $ 为题面中的"关键点"，等价于二叉树的根的左子树大小为 $ x-2 $ 。
于是，若要使 $ x $ 成为关键点，只要将中序遍历中第 $ x-1 $ 个点通过旋转操作转到根即可。
这可以使用 splay 做到均摊 $ O((n+m) \log n) $ 次旋转操作，足以通过本题。
C：
考虑一个长为 $ n-1 $ 的排列插入 $ n $ ，有 $ n $ 种方式，且其对逆序对数的影响恰分别为 $ +0,+1,+2, \ldots,+(n-1) $ 。
使用生成函数，得到长为 $ n $ ，逆序对数为 $ m $ 的排列数为：
\[\left[x^{m}\right] \prod_{i=1}^{n} \frac{1-x^{i}}{1-x}=\left[x^{m}\right] \frac{\prod_{i=1}^{n}\left(1-x^{i}\right)}{(1-x)^{n}} \]由于 $ m \leq n $ ，所以 \(\prod_{i=1}^{n}\left(1-x^{i}\right) \equiv \prod_{i=1}^{\infty}\left(1-x^{i}\right)\left(\bmod x^{m+1}\right)\) 。
考虑五边形数定理（这辈子没想到会用这个）：
\[F(x)=\prod_{i=1}^{\infty}\left(1-x^{i}\right)=1+\sum_{i=1}^{\infty}(-1)^{i} x^{\frac{i(3 i+1)}{2}} \]于是答案转化为 $ \left[x^{m}\right] \frac{F(x)}{(1-x)^{n}} $ 。
由于 $ F $ 在前 $ m $ 项中只有 $ O(\sqrt{m}) $ 项是非 0 的，可以做到 $ O(\sqrt{m}) $ 求解单次询问的答案，总时间复杂度 $ O(n+T \sqrt{m}) $ 。
标签：总结,10,right,frac,infty,二叉树,prod,模拟,left From： https://www.cnblogs.com/Mitishirube0717/p/18445666