CF461E Appleman and a Game
首先如果 \(s\) 给定判断能否匹配就是在后缀树上贪心，因为有单调性所以可以考虑处理出操作若干次能得到的最长的 \(s\) 的长度 . 只需要对于每个 \((c_1,c_2)\) 处理出 \(c_1\) 开头且后面加一个 \(c_2\) 就不是子串的最短子串长度 \(w_{c_1,c_2}\)，然后求答案时合并若干个这样的结构，转移是 \((\min,+)\) 矩阵乘法 . 此处可以倍增进行这个过程 .
这里并不需要真的建出完整的后缀树，注意到每个子串的长度大于 \(\log_{|\Sigma|}|t|\) 时一定不优，所以可以在 Trie 上依次插入每个后缀并在 \(\log_{|\Sigma|}|t|\) 深度处截断 .
CF925C Big Secret
注意到一个位置合法当且仅当它的最高位在前面为 1 的个数是偶数个，那么按最高位从小到大排序贪心插入即可 .
时间复杂度 \(\tilde O(n)\) .
CF444E DZY Loves Planting
考虑一下怎么判断 \(f(P)\ge x\)，把边权 \(\ge x\) 的边删掉形成若干连通块，每个点只能和与自己不在同一个连通块内的点匹配 . 那么只需要判断每个连通块内的 \(x_i\) 之和是否小于其它连通块的 \(x_i\) 之和即可 .
这里注意到 \(f(P)\) 肯定是某个边权，所以只需要按顺序加入每条边然后并查集维护连通块即可维护 .
时间复杂度 \(O(n\alpha(n))\) .
CF446E DZY Loves Bridges
相当于矩阵 \(B_{i,j}=\operatorname{lowbit}(i-j)=\operatorname{lowbit}(i\oplus j)\) 其中 \(\operatorname{lowbit}(0)= 0\)，给列向量 \(\bm v\) 求 \(B^t\bm v\) .
注意到令大小为 \(2^m\) 的 lowbit 矩阵为 \(B_m\) 则有：
\[B_m=\begin{bmatrix}B_m&B_m+(2^m-1)I\\B_m+(2^m-1)I&B_m\end{bmatrix} \]二阶矩阵的幂对角化一下就能求了（此处矩阵对称一定可以对角化），那么回代到矩阵乘法的式子里每次可以让问题规模减小一半，这样分治即可在 \(O(2^m+m\log t)\) 的时间复杂度内完成问题 .
CF763D Timofey and a flat tree
直接维护树 Hash，每次根移动一步只会改 2 个结点的 Hash 值 .
CF1181E2 A Story of One Country (Hard)
矩形划分过程是一个分治的模式：每次找到任意一条水平或垂直的不过任何关键矩形的直线然后分割 .
考虑直接模拟分治流程，此处划分的时候用一下启发式：从四个方向同时往对面扫，这样一个分割点一定是由离它最近的那个边界扫到，这样就可以保证每次只需要处理分割点两侧较小的那一部分 .
时间复杂度 \(O(n\log n)\) 或 \(O(n\log^2n)\)，取决于实现方式 .
CF788D Finding lines
每条直线都和 \(y=x\) 相交，考虑在 \(y=x\) 上分治：对于区间 \([l,r]\) 中点 \(x\) 查询 \((x,x)\) 的答案 \(k\)，并分治进入 \([l,x-\min\{k,1\}],[x+\max\{k,1\},r]\) .
查询之后取一个不在任何线段上的点 \((p,p)\)，对于每个线段上的点 \((x,x)\)，只需要查询 \((x,p),(p,x)\) 即可知道 \((x,x)\) 上有没有垂直或者水平的直线 .
可以简单分析到交互次数不大于 \(7(n+m)\) 次，实际上界较松 .
CF1392H ZS Shuffles Cards
对于每张牌 \(x\) 记 \(P(x)\) 表示它后面第一张 JOKER 的是第几张抽出的 JOKER . 那么设抽出一次 JOKER 的期望步数是 \(T\)，答案就是 \(T\cdot\mathbb E(\max P(x))\) .
使用 min-max 容斥转为对于每个子集算 \(\mathbb E(\min P(x))\)，此处对一轮以 JOKER 结尾的抽牌做 SEQ 构造就可以了 .
标签：log,狂练,复杂度,矩阵,JOKER,Loves,DZY From： https://www.cnblogs.com/CDOI-24374/p/18522903