*QOJ2668 论战捆竹竿
\(p,q\) 是周期且 \(p+q\leq n\) 可以说明 \((p,q)\) 是周期：令 \(p>q\)，只需说明 \(p-q\) 是周期后使用辗转相减。考虑 \(1\leq i\leq n-(p-q)\)，若 \(i>q\)，则 \(s_i=s_{i-q}=s_{i-q+p}\)；若 \(i\leq q\)，则 \(s_i=s_{i+p}=s_{i+p-q}\)。
长度 \(\geq\frac n2\) 的 border 构成等差数列：考虑最长且 \(\geq\frac n2\) 的 border \(n-p\) 和另一 \(\geq\frac n2\) 的 border \(n-q\)（\(p<q\)），此时 \(n-(p,q)\) 也是 border，由于 \(n-p\geq n-(p,q)\)，因此 \(p\leq(p,q)\)，有 \(p|q\)。对于任意 \(k\times p\leq q\) 均为周期，因此所有 \(\geq\frac n2\) 的 border 构成公差为 \(p\) 的等差数列。进一步考虑长度 \(<\frac n2\) 的 border，所有 border 均为其中最长 border 的 border，所以归纳得到所有 border 构成 \(O(\log n)\) 段等差数列。
回文串 \(s\) 的前缀 \(s'\) 回文的充要条件是 \(s'\) 是 \(s\) 的 border。
这个题的暴力做法是拿出所有周期跑同余最短路，时间复杂度 \(O(n^2)\)。注意并不能直接对于每段等差数列取最小的周期，因为只有长度 \(\leq\frac n2\) 的周期满足等差数列每项是首项的倍数，其它等差数列没有保证。考虑只有一个等差数列的情况，我们发现此时的情况实际上是一条 \((0,0+d,0+2d,\dots)\) 的链，因为必然有 \(dis_0=0\)，\(id\to jd\) 的转移代价是 \(x+(j-i)d\)，可以使用单调队列维护这个 1D-1D 的 dp。有多个等差数列时，我们从小到大处理每个等差数列，考虑模 \(s\) 时的数组 \(a\) 怎么变成模 \(s'\) 时的数组 \(a'\)。\(a_i=b\) 的意义是 \(b+ks\) 都能被拓展出来，首先用 \(b\) 更新 \(b\bmod s'\)，然后新加若干 \((b+ks,b+(k+1)s,s)\) 的边跑同余最短路。现在的问题是，有两组环，一组是当前等差数列的环，一组是上一个等差数列的遗产，从组合意义上考虑，这实际上是一个完全背包问题，因此依次对每种物品做背包是没有问题的。总时间复杂度 \(O(Tn\log n)\)。感觉组合意义的理解本质上和 [同余最短路的转圈技巧](同余最短路的转圈技巧 - 洛谷专栏) 差不多。
*SDOJ1193 矩乘游戏
给定 \(n\) 阶方阵 \(A\)，对于 \(i=1\sim n\) 查询 \(\#j\in[L,R],A^j_{1,i}>0\)。\(L,R\leq10^{15}\)，\(n\) 好像是 \(100\) 来着。
考虑组合意义，变成图上问题，相当于查询 \(A^j_{1,i}=1\) 相当于存在 \(1\sim i\) 长为 \(j\) 的路径。图为 DAG 的情况只需暴力模拟 \(n\) 轮。否则考虑用某个 SCC 增广某一条路径，暴力模拟 \(2n^2\) 轮之后，一个 SCC 能增广的形式就已经固定下来了。因为对于一个 SCC，我们只关心 \(([1,n],[0,l),0/1)\) 代表在哪个点，路径长度模 \(l\) 为多少，是否经过该 SCC。状态只有至多 \(2n^2\) 个。这个东西可以 \(O(n^4)\) 处理出来，暴力 bfs 即可。接下来要对于每个 \(i=1\sim n\) 解决：有多少 \(m\in[L,R]\)，满足 \(\exist j,m\bmod l_j\in S_j\)。容斥，变成 \(\prod [m\bmod l_j\in\overline{S_j}]\)，可以爆搜以后 excrt 合并，能有 \(70\) 分。如果 \(|\overline{S_j}|\) 很大的话就容斥回去变成 \(1-[m\bmod l_j\in S_j]\)，这样会除掉一些 \(2\) 的常数，稍加卡常即可通过。
CF1844G Tree Weights
增量构造，不过是按位。考虑变成 \(d_i+d_{i+1}-2d_{a_i}=b_i\)，按位构造，即从 \(\bmod2^k\) 推向 \(\bmod2^{k+1}\)。有 \(d_{i,k+1}+d_{i+1,k+1}-2d_{a_i,k}\equiv b_{i,k+1}\pmod{2^{k+1}}\)。最后检查一下是否合法即可。
QOJ895 Color
容易注意到合法需要每种颜色构成一个完美匹配，所以有必要条件 \(m+1\) 为偶数且 \(p_c\leq m-n+1\)。这是充分的，增量构造。每次加入一个点使得该条件仍然成立，建立二分图，左部点为颜色，右部点为先前的点。要求右部点必须匹配满，左部点中有一些点必须匹配，这个事情不是很好约束。在右部建立一个虚点，代表不匹配某种颜色，则令其接受 \(m-n\) 个匹配，此时二分图的完美匹配就是一个合法方案。这个二分图必然存在完美匹配，直接流即可。考虑我们实际上可以将这个图补成正则二分图，应用霍尔定理，\(k\) 正则二分图任意左部点集合发出 \(k\times |S|\) 条边，所以 \(|N(S)|\geq|S|\)。
QOJ15303 Basic Counting Practice Problems
写出 \(O(n^4)\) 的二维树上背包，注意到第三维是卷积，改成插值后可以 \(O(n^3)\) 维护 dp。不过求答案需要插回去之后乘上权值向量的转置，但我们知道插值也是一个线性变换，于是可以提前预处理出来插值矩阵乘上权值向量的转置，这样只需要向量乘法就能维护答案。时间复杂度 \(O(n^3)\)。
好像也可以将所有要统计的多项式放到一起拉插，这样只有 \(n\) 次往回插的操作。
*QOJ5022【模板】线段树
容易解决 DE 性质：替换为异或差分操作便于刻画，由 Kummer 定理得到的经典结论是 \(k\) 轮过后 \(a_j\) 对 \(a_i\) 产生贡献当且仅当 \((i-j)\subseteq k\)，使用 FWT 状物即可解决问题。
线段树完全无法维护这件事情，不过我们发现 \(k=2^c\) 时性质十分良好。于是按照 \(B=2^c\) 进行操作分块，此时对于全局修改每块都能 \(O(n)\) 维护变化。当修改变成区间以后，尝试分块维护。为了保持每个位置只和前面不是很多的位置存在联系，操作分块后按照再按照 \(B\) 对序列分块。这样若 \((i,i+1)\) 两块被整体操作，\(i+1\) 这一块就能相对轻松地维护。具体来说，扫描序列上的每块，如果一次修改完全包含了 \((i-1,i)\) 则打标记；若只包含了部分则重构 \(i-1\) 和 \(i\) 后暴力修改。询问时直接枚举 \(k\) 的子集进行查询。这样做的道理在于，操作分块后 \(i+1\) 块确实只和 \(i\) 块相关，如果在某次修改中 \(i\) 的某个位置维护错了也不用管，因为此时这个位置必然不会再影响到 \(i+1\) 块。这样每次修改重构 \(O(1)\) 块，每块时间复杂度 \(O(B\log B)\)，总时间复杂度 \(O(q\sqrt n\log\sqrt n)\)。
代码源 NOI Day7 Afterimage
区间查询可以变成单点查询：维护前缀异或，此时操作二不变，操作一变成删去最后一个数同时在开头插入原序列第一个数。操作分块，考虑此时除了一段前缀，中间很长的区间都不会很受操作的影响，只和前面 \(B\) 个数有关。于是每次修改对开头一段固定区间暴力重构即可。
MX NOI Day4 A 小 Z 的传送带
直接的想法是扫描纵坐标，线段树维护每个横坐标的答案，但是这样做每次需要更新太多位置。考虑维护纵坐标 \(\leq y\) 时传送带组成的轮廓线上的答案，这样新加入一条传送带时只需考虑左右端点处的答案变化。线段树上维护 \(ans-k\times i\) 和 \(ans+k\times i\) 即可。注意到并不需要在这两棵线段树上更新 \((L,R)\) 这段区间的变化，因为 \(-k<v<k\) 保证了左右端点处一定更优。感觉细节挺多的。
*P15383 一千年以后
拆贡献到每种颜色上，建虚树。注意到答案是连通块数量-虚点连通块数量，前者点边容斥，限制可以写成二维数点。后者没法很好地用点边容斥处理，考虑钦定虚点连通块中深度最浅的为代表元，数代表元。这样如果一个虚点如果连到父亲或者子树内的实点就爆了，考虑限制是给定区间集合 \(S\)，不能包含 \(S\) 中的任何一个区间，对支配对做一手启发式合并大概可以 \(2\log\)。
实际上考虑合并区间的过程，可以发现每个点上只会保留 \(O(1)\) 个区间，剩下都被支配掉了，所以我们暴力合并即可，时间复杂度 \(O(n\log n)\)。
*MX NOI Day7 C 全军出击
神人基于值域做法，感觉把基于论文的 std 干爆了。首先给出的是半群，虽然没法直接容斥了，但是我们注意到仍然可以通过容斥求出每种权值对答案的贡献次数，时间复杂度 \(O(256\times 2^7\times n)\)。发现修改的复杂度只是 \(O(2^7\times n)\)，考虑怎么平衡一下，这个 \(256\) 肯定是作为一个整体，于是尝试减小查询复杂度中 \(2^7\) 这一项。提取出前八个质因子 \(\{2,3,5,7,11,13,17,19\}\)，剩下最多三个质因子。查询时只对大质因子集合容斥，在大质因子集合有交的情况下是好处理的，无交的话还需要再做一步容斥，总之看上去怎么对就怎么做好了。容易平衡到修改 \(O(8\times2^8)-O(8\times 256)\)。空间问题扫描值域逐个数处理即可。
*QOJ8739 寒蝉鸣泣之时·业
真是神了啊。我们将操作序列的 \((pos,x)\) 两维进行对偶，按照 \((-x,y)\) 进行排序。这样问题变成提取一些合法的下标求 \(y\) 前缀和的最大值。分块后使用 D2T2 的技巧做到 \(O(n\sqrt n)\)。亦可用 KDT 维护，不过常数很大。这告诉我们 KDT 和 D2T2 有互通之处。
HT-107-NOI B 最小生成树
使用 The King's Guards 的方法建立重构树后容斥，考虑问题实际上变成了一个二维数点。启发式合并可以说明只有至多 \(O(n\log n)\) 个需要进行数点的区间。考虑启发式合并的过程中如何维护区间权值，打标记就好了。时间复杂度 \(O(n\log^2 n)\)。感觉也可以二离莫队做到根号。
SDOJ1198 迪艾斯
题意是啥来着。
\(2,4,p^k,2p^k\) 存在原根，求出原根 \(g\) 后转化为指数加法。答案为 \(\frac{p-1}{\gcd(b_1,b_2,\dots,b_n,p-1)}\)，看上去必须避开求阶，因此考虑直接维护 \((b_i,p-1)\)。我们考虑 \(x=g^{b_i}\)，令 \(x\) 的阶为 \(c_i\)，则 \(b_ic_i\equiv0\pmod{p-1}\)，同时 \(c_i\) 是满足此条件的最小正整数。容易得到 \(c_i=\frac{p-1}{(b_i,p-1)}\)，因此 \((b_i,p-1)=\frac{p-1}{c_i}\)。接下来只需要线段树上维护区间修改区间 \(\gcd\)，经典做法是差分维护 \(\gcd(a_i,a_{i-1})\)，这样只需要单点修改区间 \(\gcd\) 即可。求阶可以枚举 \(\varphi(p)\) 的所有质因子，每次尝试去掉一个。时间复杂度 \(O(n\log p)\)。区间 \(\gcd\) 是 \(1\log\) 的。
🤮SDOJ1205 众数很爽
区间权值为区间内颜色出现次数极差，求权值最大的区间权值。可能是 \(n\leq2\times 10^5\)。
考虑暴力如何不带 \(\log\)。固定一种颜色的权值为 \(1\)，枚举其它颜色，将权值设为 \(-1\)，要求包含 \(-1\) 的最大子段和。这个可以使用类似最大子段和 dp 的方法扫描 \(-1\) 的连续段，时间复杂度 \(O(n^2)\)，不过发现实际上固定颜色后可以做到 \(O(\min(x,y))\)。据此进行根号分治，如果两种颜色中有任意一种 \(>B\) 的，那么用相同的方法做到 \(O(\frac{n^2}B)\)。否则只有 \(O(nB)\) 种可能成为答案的区间，暴力枚举这些区间，现在要求判定区间众数出现次数是否 \(\geq x\)。注意到这个关于左端点单调，在每个右端点处预处理每个 \(x\) 最大的合法左端点，直接判定即可。时间复杂度 \(O(n\sqrt n)\)。
*CF1280F Intergalactic Sliding Puzzle
研究了官方题解一整天没研究明白怎么构造三轮换，所以不管了，这里写的是 Phartial 的做法。题目给出的结构并不是很利于构造，考虑加强成一些比较清晰的结构。再手玩“如何移动一个数到某个位置”这一过程后，我们发现这个过程和环很相关。将空格移到中间一列，这样问题变成有两个在某个点相交的环，每次可以 shift 一个环，构造方案。分别构造两个环。左环看上去随便怎么构造一下就好了，我们先把需要的数扔到右环上，然后将左环转成一个比较对的样子，再转回来。接下来考虑右环，如果我们按照同样的构造方法，可以发现对左环也没有非常大的影响，当操作次数为偶数的时候正好没有影响。相当于要求右环需要是偶置换，研究一下官方题解，发现所有能做的操作都是偶置换，所以只有偶置换合法。
ARC180E LIS and Inversion
也不会做。
ARC186F 记得做
不会做，玉玉症。最小费用最大流可以通过求出最大流后增广负环得到。