哇塞怎么 2021 年了，怎么我还是那么菜。qwq
这个月做题重心在 SAM、数据结构。
因为疫情被封在学校很自闭，这个月做题很少啊，文化课也开始拖后腿了。
8日
P3181 [HAOI2016]找相同字符
广义SAM。
把两个串插入广义SAM里，对于两个串分别维护不同的 \(size_0,size_1\)，然后在 parent 树上统计，最后答案是 \(\sum_u size_0(u)\times size_1(u)\times (len(u)-len(link(u)))\)。
9日
CF666E Forensic Examination
广义SAM + 线段树合并。
把 \(S\) 串和所有 \(T\) 串插到 SAM 里，SAM 每个节点维护一棵线段树，记录在 \(T_{1\dots n}\) 的出现次数，建出树来再线段树合并。对于每个询问，在 parent 树上倍增找到对应节点，查线段树即可。
pair 慢死了，跑了五十多秒。
P3346 [ZJOI2015]诸神眷顾的幻想乡
广义SAM。
一个显然的性质：对于树上任何一个路径，一定能找到一个点，使得一该点为根时，该路径是直上直下的。
数据限制叶子很少，就对于每个叶子为根的几棵树当成 trie 树，插到一个 trie 里。
在 SAM 里离线构造，就是数本质不同子串个数的裸题了。
10日
P6292 区间本质不同子串个数
SAM + LCT + 线段树。
类比静态区间数颜色数：最于每种颜色记录 \(last_i\) 表示最晚出现位置，线段树维护区间和，询问离线后，扫描线处理，每加入一个点 \(i\) 就让 \(last_{c_i}\) 贡献 \(-1\)，\(i\) 位置 \(+1\)。
现在同样离线询问，扫描线时在结尾加入点 \(i\)，产生的子串是目前所有的后缀，我们需要让这些子串的 \(last\) 贡献 \(-1\)。
先把整个串 \(S\) 建出 SAM，然后在 parent 的树上后缀 \(S[1,i]\) 对应节点的所有祖先（一条链）就是以 \(i\) 结尾的所有后缀，不能暴力跳，想到用 LCT 维护 parent 树结构。
可以发现这条链上相邻节点代表子串的右端点相同，左端点连续。那么在 LCT 的 access 操作时，对于这条链上每一段在线段树区间修改，同时标记新的 \(last\)。最后加上当前所有后缀的贡献即可。
复杂度 \(\mathcal O(n\log^2 n + q\log n)\)。
SP1811 LCS - Longest Common Substring
SAM。
求最长公共前缀，就是对于 \(T\) 的每一个前缀，找到其最大的后缀是 \(S\) 的子串。
那么把 \(S\) 建出 SAM，然后在 SAM 上沿着 \(T\) 走，每走一步匹配长度加一，若走不动了，就跳 \(link\)，匹配长度缩小到 \(link\) 节点的 \(len\)，每一步的匹配长度取最大值即可。
除去建立 SAM 的复杂度，该部分复杂度 \(\mathcal O(|T|)\)。
11日
SP1812 LCS2 - Longest Common Substring II
广义SAM。
和上题类似，把所有串扔进SAM里，然后我们随便找一个串来在SAM里匹配，并且只走在所有串中都出现过的节点（分别维护 \(size\)）。
14日
P4218 [CTSC2010]珠宝商
见 题解。
16日
2824 [HEOI2016/TJOI2016]排序
线段树分裂 + 线段树合并。
每一个区间维护一棵权值线段树，每次排序就是把边界的区间线段树分裂，然后把这些区间的线段树合并，注意正序和倒序。
另外开一个 set 维护这些区间的左端点，便于查找所在区间。
复杂度是 \(\mathcal O((n+m)\log n)\)，证明见 FlashHu 的题解。
P6186 [NOI Online #1 提高组] 冒泡排序
树状数组。
设 \(f_i\) 表示 \(j<i,a_j>a_i\) 的 \(j\) 的个数，观察冒泡排序的性质，每轮冒泡会让所有不为零的 \(f_i\) 减一。所以查询答案就是 \(\sum_{i=1}^n[f_i>k]f_i-k\)。
交换操作只会改变相邻两个的 \(f\) 值，很好处理。
逆序对个数上限是 \(n^2\) 级别的，又忘了开 long long。
P6478 [NOI Online #2 提高组] 游戏
树形DP + 二项式反演。
设 \(G(i)\) 表示恰好 \(i\) 对点匹配的方案数，不好计算，就再设 \(F(i)\) 表示至少 \(i\) 对点匹配的方案数，就可以二项式反演： \[ F(k)=\sum_{i=k}^n\binom{i}{k}G(i)\Leftrightarrow G(k)=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}F(i) \] 现在考虑 \(F(i)\) 怎么算。设 \(f(u,i)\) 表示以 \(u\) 为根的子树至少 \(i\) 对点匹配的方案数，\(sum_0(u),sum_1(u)\) 表示以 \(u\) 为根的子树里白/黑点的个数，树形DP。先背包合并： \[ f_*(u,i+j)=\sum_{i=0}^{size(u)}\sum_{j=0}^{size(v)}f(u,i)\times f(v,j) \]
然后假设 \(u\) 为黑点（白点同理），选出子树里未匹配的白点匹配： \[ f_*(u,i+1)=f(u,i+1)+f(u,i)\times (sum_0(u)-i) \]
DP 之后 \(F(i)=f(1,i)\times(n-i)!\)（剩下的点任意匹配）。总复杂度 \(\mathcal O(n^2)\)。
17日
CF840D Destiny
主席树。
\(k\) 很小，先建立主席树，维护权值区间内的数出现次数和。差分得到区间，每次尽量走可能有答案左区间。
复杂度 \(\mathcal O(nk\log n)\)，相当于 \(k\) 次单点查询。
P5459 [BJOI2016]回转寿司
离散化 + 树状数组。
前缀和一下，其实就是找 \(j<i\) 且 \(s_i-R\le s_j\le s_i-L\) 的 \((i,j)\) 点对个数。
离散化记得把 \(s_i-L\)，\(s_i-R-1\) 一块离散化，用 unordered_map 留下映射关系，然后就可以上树状数组了，复杂度 \(\mathcal O(n\log^2n)\)。
CF896C Willem, Chtholly and Seniorious
珂朵莉树。
就是将相邻的相同元素作为一个元素，用 set 维护，各种操作暴力。只有在有区间推平操作且数据随机的情况使用，此时复杂度接近 \(\mathcal O(n\log n)\)。
P1856 [USACO5.5]矩形周长Picture
扫描线。
求矩形并的周长。先纵向扫描线，同一纵坐标的线段保证先加后减，每操作一条线段增加的答案是覆盖长度变化值的绝对值。横向再做一遍就好了。
CF558E A Simple Task
珂朵莉树。
比 CF896C 还简单，直接用长为 26 的数组维护。
21日
AT2062 [AGC005D] ~K Perm Counting
容斥 + DP。
设 \(F(i)\) 为有 \(i\) 个位置不合法的方案数，容斥（反演）一下就是求 \(\sum_{i=0}^n(-1)^iF(i)\)。
要求 \(F(i)\)。每个位置 \(i\) 放 \(i-k\) 或 \(i+k\)，会影响到其它的位置。
把坐标看作一列点，值也看成一列点，点 \(i\) 和值 \(i\pm k\) 连边，可以发现这是个二分图上 \(2k\) 条链。
要选 \(i\) 个点不合法，也就是坐标点向值点连边，但是坐标点和值点都至多连一条边。
把所有链拎出来并连成一条 \(2n\) 的大链，设 \(f(i,j,0/1)\) 表示前 \(i\) 个点连了 \(j\) 条边并且 \((i-1,i)\) 这条边是否连上的方案数。
转移就很简单了： \(\begin{cases}f(i,j,0)=f(i-1,j,0)+f(i-1,j,1)\\f(i,j,1)=f(i-1,j-1,0)\end{cases}\)，注意 \(i\) 为链的开头时 \(f(i,j,1)=0\)。
那么 \(F(i)=(f(2n,i,0)+f(2n,i,1))\times (n-i)!\)，其中 \((n-i)!\) 表示合法的点随便放。
复杂度 \(\mathcal O(n^2)\)。
22日
P4097 [HEOI2013]Segment
李超线段树。
板子题。就是用线段树每个节点维护包含该区间最优线段（暴露在最高折线中横坐标跨度最大），插入线段时与原最优线段对交点分类讨论，查询就用 \(\log n\) 个节点的最优线段都更新一遍。
具体见 George1123 的题解。
每插入一条线段，会分到 \(\log n\) 个节点里，而每个节点都需要 \(\mathcal O(\log n)\) 的时间对所有子区间判断新线段是否为最优线段，所以单次插入复杂度 \(\mathcal O(\log^2 n)\)；查询显然 \(\mathcal O(\log n)\)。
23日
P4198 楼房重建
分块（正解是线段树）。
显然每个点转化成斜率。分块的话每个块内维护一个单调递增的序列，序列上二分来合并每个块，复杂度 \(\mathcal O(n\sqrt{n}\log n)\) 或者 \(\mathcal O(n\sqrt{n\log n})\)，实测前者更快。
线段树做法是维护区间最大值的该区间答案，每次合并两个区间就是在右区间上二分，复杂度 \(\mathcal O(n\log^2n)\)。
26日
P2056 [ZJOI2007]捉迷藏
括号序 + 线段树。
将树的 括号序 弄出来，然后我们知道两点在括号序上的位置 \(pos_u,pos_v\) 之间未匹配的括号数就是距离。去掉匹配的括号，剩下的就是左边若干 ) 和右边若干 (，数目记为 \(a,b\)。
我们要求黑点之间最大距离，可以类似“最大子段和”用线段树维护。
两个区间合并，左区间是以黑点开头的后缀（\(a_r,b_r\)），右区间是以黑点结尾的前缀（\(a_l,b_l\)），合并就是 \(a_r+b_l+|b_l-a_r|\)，也就是 \(\max(a_r+b_r-a_l+b_l,~a_r-b_r+a_l+b_l)\)。
设 \(lmax_1\) 为前缀最大 \(a+b\)，\(lmax_2\) 为前缀最大 \(b-a\)，\(rmax_1\) 为前缀最大 \(a+b\)，\(rmax_2\) 为前缀最大 \(a-b\)，就可以维护了。
这道题还可以用动态点分治做。
28日
SP2916 GSS5 - Can you answer these queries V
猫树。
其实是可以线段树做，每次询问对于区间 \([l_1,r_1]\)、\([l_2,r_2]\) 是否重叠、答案区间的两个端点是否在重叠区间，分类讨论一下。
猫树讲解。为了练一下猫树，考虑把线段树换成猫树。猫树上就需要维护端点到 \(mid\) 的权值和、包含端点的最大子段和，以及两者的前缀最大值。虽然单次询问变成 \(\mathcal O(1)\) 了，可惜在这题没啥优势。
AT2370 [AGC013D] Piling Up
计数DP。
设白球 \(x\) 个，则黑球 \(n-x\) 个，cc 表示两次取球颜色，手玩一下，可以发现：
00：\((x,n-x)\rightarrow(x-1,n-x)\rightarrow(x-1,n-x+1)\)；01：\((x,n-x)\rightarrow(x-1,n-x)\rightarrow(x,n-x)\)；10：\((x,n-x)\rightarrow(x,n-x-1)\rightarrow(x,n-x)\)；11：\((x,n-x)\rightarrow(x,n-x-1)\rightarrow(x+1,n-x-1)\)。
设 \(f(i,j)\) 表示走 \(i\) 步有 \(j\) 个白球的方案数，直接 DP 发现会重，因为 \(x\) 状态序列为 1 2 3 和 2 3 4 产生的操作序列一样。
这里有个技巧，只统计经过最小值的方案。00 和 01 操作过程中 \(x\) 值是会变小的，当 \(x=0\) 时就没法通过这两个操作转移了，所以最小值就是 \(0\)。
那么设 \(f(i,j,0/1)\) 表示走 \(i\) 步有 \(j\) 个白球、是否经过 \(x=0\) 的方案数，初始状态注意 \(f(0,0,1)=1\)，\(f(0,i,0)=1\)。
另外注意 00 操作是不能在 \(x=0\) 处转移的。最后复杂度 \(\mathcal O(nm)\)。
31日
BZOJ#2870 最长道路tree
边分治。
类似点分治，找到最接近重心的边，分成两棵子树来处理，相比点分治的优势就是处理答案简单，且不需要麻烦的容斥。不过会被菊花图卡，所以需要三度化处理。
对于这道题，就是统计答案时维护距离和路径最小值，然后双指针扫两遍。
具体地最好看 代码。