今天也是好起来了，终于赛时大于100分了
今天的题目全是从CCPC或ICPC中找的，搬题人也是神人，在每题里面硬加了一些星露谷元素，硬是成为了星露谷专场，不得不说还挺成功，我差点就找不到原题了
讲题的也挺逆天，共讲90分钟，T4独占一个小时,改题也是改到了300分
有些题目他在原题的基础上加了多测或一些奇奇怪怪的东西在此不做说明，因为思路是一样的
Ps：放代码太麻烦了，不放了
T1
题目传送门(gym104869J)
这题一看题目就没有想打的欲望，看到树两眼一黑，看到题目解释的"同构"的概念(解释的足够抽象)立马换到下一题
但最后无聊回来手玩这一题的样例，发现这题真简单，我差点就被题意骗了
因为他要求前后操作的树不同构，不难发现，我们只能选两个不是叶节点的节点，而每次操作后一个节点会变成叶节点，另一个节点的度数会增加，所以每次操作相当于多了一个叶节点
也不难发现，但有n – 1个叶节点是游戏结束,所以这一题只要枚举刚开始不是叶节点(度数 > 1)的节点个数，在判一下奇偶性就结束了，若非子节点数是奇数输出后手者，偶数输出先手者
要特判n = 2的情况，此时要输出后手者(你猜我赛时是怎么95pts的)
T2
题目传送门(gym101986F)
不会改了
T3
先不考虑修改，只考虑对于一个特定的区间，我们如何快速地去回答任意给定的k
将一个区间划分成K段就是一个隔板法。但此处我们有限制，对于S_{i + 1} \leq S_i的位置，我们必须插入一个隔板，否则就是不合法的。所以对于一个区间，我们只要知道了该区间有多少个位置必须要插入隔板，我们就可以快速回答任意的K：假设区间中有N个空位，X个必须要插入隔板的位置，
则答案就是 C_{N – X}^{(K – 1) – X}
只用特判掉一些答案为 0 的情况就好了
而且我们发现，对于两个区间的合并也是比较简单的：只用将两个区间的 X 相加，然后判断下两个区间合并是否会产生新的必须要隔板的位置就好了
接下来只需要解决如何修改，我们就可以用线段树来实现了
为了方便处理修改，首先把 ABCD 变成 0123，这样修改一次区间中的数 x 就变成 (x + 1) \% 4
我们只用维护必插位置的数量。而且手玩一下就可以发现，只有使区间端处的 3 变成 0 的修改，才有可能改变必插位置的数量。具体的若最前面的是 3 则修改后少一个，若最后面是 3 则修改后多一个
于是，上述修改方法配合lazy \quad tag我们就可以实现区间修改了
对于组合数，预处理以下阶乘和阶乘逆元就好了
T4
题目传送门(gym104869D)
先枚举p的长大于q的长,就会是aba + b的形式
那么a的最大长度就是LCP(s,t) (最长公共前缀)
b的最大长度就是LCS (最长公共子序列)
所以可以差分预处理出所有的LCS和LCP
差分预处理后求出前缀和皆可以直接统计出答案
做完这种可能之后直接swap(s, t)就可以得出另一种可能的数量了