单位根反演不会啊怎么搞 $FFT$ 吧，还是了解了单位根反演后才可以搞的好吧……居然有人吐槽我说我学了 $FFT​$ 但是不会运用？！，嘤嘤嘤打击有些大……

实际上所谓的单位根反演就是这个东西：

$$\frac{1}{n}\sum_{i=0}^{n-1}(\omega_n^d)^i=[n|d]$$

$myy$ 出的神题……貌似正解并不难但是没有人切……

$30$ 分可以用 $DP$ ，设 $f[i][j]$ 表示 $i$ 到 $j$ 是否有一条满足条件的路径。对于有一条满足条件的路径的 $i,j$ ，我们枚举连接 $i$ 的点和连接 $j$ 的点，如果这两个点的标记相同，那么既然 $i,j​$ 合法，这两个点也一定合法。

不过这样的复杂度是 $O(m^2)$ 的，所以只能过 $30$ 分。

细节诸多…………

$gcd$ 显然可以用线段树维护，但是如果是区间修改的话就不好办了。这个时候我们需要将原矩阵以棋盘守护者的位置为中心进行差分，那么区间修改就变为单点修改了，$gcd$ 自然好维护多了。

$\texttt{HNOI2019}$ 终于改出来一道题目了……感谢 $JerryC$ 跟我一起讨论，不然我也看不懂题解。这题真的是 $\texttt{HNOI2019}$ 最可做的题啊，可想而知 $\texttt{HNOI2019}$ 有多么毒瘤了。

$orz yyb$ ，感谢 $yyb$ 大佬的题解。

这一题一共有两问，并且部分分也比较多，接下来我们一起来逐一攻破这些特殊条件。

后缀数组。

假设我们现在已经求出了 $height$ 数组，我们发现，对两个后缀，其重复了的字串的个数就是 $height$ 数组所记录的数。我们举个例子：

后缀$sa[i-1]$: $aaabbdbs$
后缀$sa[i]$ : $aabbdbs$

我们设 $n \leq m​$ ，然后开始推式子，我们将 $gcd(i,j)​$ 的值作为 “$d​$” 提出来：

$$\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$$ $$=\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}if(gcd(i,j)=d) f[d]$$ $$=\prod_{d=1}^{n}\prod_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\prod_{j=1}^{ \lfloor\frac{m}{d}\rfloor }if(gcd(i,j)=1) f[d]$$ $$=\prod_{d=1}^{n} f[d]^{\sum_{i=1}^{ \lfloor\frac{n}{d}\rfloor }\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]}$$

本文为加密文章，阅读本文需要输入密码。

实际上可以用平衡树做的但是不喜欢平衡树。

还是喜欢可爱的线段树，于是打了一发线段树合并。很久没有这样子的做题感觉了，真是美妙，思路清晰，交上去一遍过(窝不会告诉泥萌窝第一次交的时候忘关文件=。=)。

三道题目，一眼出算法。

第一道题目显然是后缀自动机，
第二道题目显然是莫比乌斯反演加上杜教筛。
第三道题目显然是网络流。

然而考场上都没做出来……自闭了。

真的，现在已经是傍晚了，大后天就是毒瘤的省选了……小学中现在正在举办运动会，班级群中一群人在那里一个劲的喊加油，但是，班上有人给我加油吗？除了几个好朋友之外……

神奇的题目。

网上说什么做了这道题 $Splay$ 就差不多了，嗯对窝也这么觉得。于是终于码掉了。

主要涉及的操作还是提取区间，我们组需要将 $l-1$ 提取至 $root$ ， 然后将 $r+1$ 提取至 $l-1$ 的下方，最终询问的 $l,r$ 区间的 $Splay$ 就是 $r+1$ 的左孩子。