签到题，求输入的数中不是平方数的最大的数是多少。居然因为打漏了一个等号fst了!

B. Conan and Agasa play a Card Game

题目大意：

Conan和Agasa玩游戏，有\(n\)种卡片，第\(i\)种卡片有\(a_i\)张，两人轮流操作，每次操作选择一张剩下的卡片，将它和所有数量比它少的种类的卡片都删掉，无法进行操作的人输。Conan先手，问双方都采取最优策略的情况下谁会获胜。

题解：

显然只要有一种卡片的数量是奇数，就是先手赢，否则后手赢。

C. Travelling Salesman and Special Numbers

题目大意：

定义\(f(x)\)为\(x\)二进制下\(1\)的个数，\(g(x)\)为\(x\)最少经过多少次\(f\)变换后会变成\(1\)。求不大于\(1\le n<2^{1000}\)的\(0\le g(x)=k\le1000\)的数的个数，对\(10^9+7\)取模。

题解：

因为\(n<2^{1000}\)，所以会对答案作贡献的数，经过一次\(f\)变换后一定不大于\(1000\)，因此可以预处理出\(1000\)以内的数的\(g(x)\)，然后枚举\(g(x)=k-1\)，去统计不大于\(n\)的二进制下有\(x\)个\(1\)的数的个数即可。

注意特判\(k=1\)时，一定会多算一个\(1\)的贡献。

题目大意：

有一个长度为\(n\le5\times10^5\)的数组\(a\)，接下来\(q\le4\times10^5\)次操作，每次操作是以下两种之一：

题解：

用线段树维护区间\(gcd\)，询问时二分找到最小的\(i\)，使得\([l,i]\)的\(gcd\)不被\(x\)整除，然后尝试修改\(a_i\)，查询\([i+1,r]\)区间的\(gcd\)，判断其是否能被\(x\)整除即可。修改则直接修改。

在线段树上二分，复杂度\(O(n\log{n})\)乘上求\(gcd\)的复杂度。

题目大意：

给出一棵\(n\le2\times10^5\)的树，每个节点都有且只有一个字符(小写字母\(a-t\))。对每一个节点，询问有多少条经过它的路径（交换起点终点算同一条路径）组成的字符串是回文的。

题解：

注意到字符只有\(20\)种，因此可以状压每种字符的奇偶性，枚举哪个字符有奇数个，树分治即可。

树分治的时候不光要统计当前重心的答案，还要顺便统计访问到的节点的答案。

注意对于非重心节点，以当前子树内的任意一个点作为端点的路径都会对它做贡献。

注意对于重心节点，有的路径在两个端点处都计算了，需要对这一部分除以\(2\)进行去重。

时间复杂度\(O(\alpha n\log{n})\)，\(\alpha\)为字符集大小\(20\).

题目大意：

给出一个长度为\(n\le10^5\)的只由小写字母组成的字符串\(s\)，之后给出\(q\)次操作，每次操作是以下两种之一：

保证第二种操作中字符串的总长度不超过\(10^5\)

题解：

因为询问的字符串总长度不超过\(10^5\)，我们可以取\(K\)约等于\(\sqrt{10^5}\)，这样操作2中长度大于\(K\)的串最多有\(\sqrt{10^5}\)个，这些串直接和\(s\)串进行一次kmp即可。

对于长度不大于\(K\)的询问串\(t\)，我们将\(s\)按大小\(K\)分块，这样就保证了\(t\)只会出现在\(s\)的某块内或者是横跨相邻两块。

对于\(s\)的每一块，维护一个sam来计算块内的出现次数，每当修改的时候重新构建这一块的sam。

对于横跨两块的部分，只需要拿出\(2(|t|-1)\)长的部分与\(t\)做一次kmp即可。

总的时间复杂度\(O(n\sqrt{n})\)，空间复杂度\(O(n)\)。