考完 NOIP 就要回去补文化课了，这个月可能做不了多少题了。
2日
S2OJ#123 数组入门
分块。
取模可能会让中间的某些值修改后变成最小值，所以要用维护权值的数据结构。
考虑分块，每个块维护一个排好序的 vector，下放标记就重构，查询就 lower_bound。
经过多次调参和提交，发现块的大小为 \(n^{0.4}\) 能 AC，复杂度 \(\mathcal O(m(n^{0.6}+n^{0.4}\log n^{0.4}))\)。
P1776 宝物筛选
单调队列优化多重背包。 \[ \begin{aligned} f(i,j)&\leftarrow \max_{0\le k\le c}\{f(i-1, j-kw)+v\times k\}\\ f(i,d+kw)&\leftarrow \max_{k-c\le k'\le k}\{f(i-1, d+k'w)-v\times k'\}+v\times k \end{aligned} \] 对于每个 \(d\ (0\le d < w)\) 分别用单调队列维护 DP，总复杂度 \(\mathcal O(nm)\)。
3日
U142829 魔法商店
物品重量很小，按重量分类再排序，转化成多重背包。
设 \(s(i,j)\) 为物品 \(i\) 最大的前 \(j\) 个物品价值和。 \[ f(i,d+kw)\leftarrow \max_{k-c\le k'\le k}\{f(i-1, d+k'w)+s(i,k-k')\} \] \(s(i,j)\) 是凸的，\(f(i,j)\) 单调不降，所以这东西有决策单调性，可以单调队列优化，或者分治。
CF220B Little Elephant and Array
树状数组 + 离线。
离散化，用 vector 把每种权值的所有位置按顺序存起来，先令区间左端点为 \(1\)，确定右端点合法范围，用树状数组区间打标记。
将所有询问离线，从左往右扫，对于以该点为左端点的询问在树状数组上单点查询；每次只有 \(1\) 种权值答案改变，在树状数组上撤销和修改即可。
总复杂度 \(\mathcal O(n\log n)\)。
U144136 距离
倍增 + 二分 + 最短路。
发现不断地往 图里加边，\(1\) 到 \(n\) 的最短路单调不升，可以二分。
考虑 \(47\) 分：对于某个时间段里的边建出图来跑最短路，二分 \(5\) 次即可，复杂度 \(\mathcal O(n\log^2n)\)。
至于满分做法，因为清空图的时间段很多，每次二分边界中有许多无用的范围，考虑用倍增缩小二分范围。
设上次清空时间点 \(D\)，倍增到最小的时间点 \(D+2^i\) 满足 \(dis(1,n)\le T\)，在中间二分并更新 \(D\)。
每条边最多被处理 \(\log q\) 次，复杂度应该是 \(\mathcal O(q\log q)\)。
毒瘤 \(\rm \color{black}{A}\color{red}{zusaCat}\)，她卡了 SPFA。
15日
P5410 【模板】扩展 KMP（Z 函数）
见 板子 kmp
16日
P1494 [国家集训队]小Z的袜子
经典莫队板子，复习。
17日
SP10707 COT2 - Count on a tree II
树上莫队，见 莫队总结。
19日
AT1219 歴史の研究
回滚莫队，见 莫队总结。
20日
P4887 【模板】莫队二次离线（第十四分块(前体)）
二次离线莫队，见 莫队总结。
P4074 「WC2013」糖果公园
树上莫队 + 带修莫队。
不太好码。
21日
P2713 罗马游戏
可并堆。
P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并
树上差分 + 线段树合并。
注意是多次路径修改并且一次询问，树上差分后把所有询问插入对应点的线段树中，dfs 一遍把每个点儿子的线段树合并到它的线段树上，然后在线段树上查即可。
插入点数 \(n\)，复杂度 \(\mathcal O(n\log n)\)。
22日
P3224 [HNOI2012]永无乡
并查集 + 线段树合并。
并查集维护连通性，线段树合并硬上即可，每次合并都没有重合的点，复杂度 \(\mathcal O(n\log n)\)。
P3919 【模板】可持久化线段树 1（可持久化数组）
可持久化线段树。
P2839 [国家集训队]middle
二分 + 可持久化线段树。
中位数套路：把大于等于 \(x\) 的设为 \(+1\)，小于 \(x\) 的设为 \(-1\)，若和为 \(1\) 或 \(0\) 则 \(x\) 为中位数。
先考虑询问固定的区间，二分最大的 \(x\) 满足区间和 \(\ge 0\)，所以需要对于每一个值开一棵求中位数的线段树。
相邻两个值的线段树只有很少几个值不同，可以通过可持久化线段树将时间空间降到 \(\mathcal O(n\log n)\)。
对于询问 \(a,b,c,d\)，\([b,c]\) 是一定要选的，查和即可；因为要让中位数尽可能大，所以 check 时的区间可也要尽可能大，所以取 \([a,b)\) 的最大后缀和、\((c,d]\) 的最大前缀和。
P1712 [NOI2016]区间
尺取法 + 线段树。
把所有区间按长度排序，然后模拟一个队列，每次向后挪动 \(r\) 至有至少一个点覆盖次数 \(\ge m\)，再尽量往后挪动 \(l\)，更新答案，覆盖次数用线段树维护。
23日
P5192 Zoj3229 Shoot the Bullet|东方文花帖|【模板】有源汇上下界最大流
有源汇上下界最大流，见 总结 网络流。
P6329 【模板】点分树 | 震波
点分树，见 总结 点分树（动态点分治）。
24日
P3345 [ZJOI2015]幻想乡战略游戏
点分树，见 总结 点分树（动态点分治）。
P3241 [HNOI2015]开店
点分树，见 总结 点分树（动态点分治）。
26~27日
写了一堆多项式板子题，见 板子 多项式全家桶。
P2260 [清华集训2012]模积和
整除分块。
令 \(n\le m\)，推式子：
\[ \begin{aligned} &\quad\sum_{i=1}^n\sum_{j=1}^m[i\not=j](n\bmod i)(m\bmod j)\\ &=\sum_{i=1}^n\sum_{j=1}^m(n-\lfloor\frac{n}{i}\rfloor i)(m-\lfloor\frac{m}{j}\rfloor j)-\sum_{i=1}^{n}(n-\lfloor\frac{n}{i}\rfloor i)(m-\lfloor\frac{m}{i}\rfloor i) \end{aligned} \]
设 \(F(n,k)=\sum_{i=1}^n \lfloor\frac{k}{i}\rfloor i\)，这东西可以 \(\mathcal O(\sqrt{n})\) 整除分块算。
\[ \begin{aligned} &=(n^2-F(n,n))(m^2-F(m, m))-\sum_{i=1}^{n}(nm-n\lfloor\frac{m}{i}\rfloor i-m\lfloor\frac{n}{i}\rfloor i+\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2)\\ &=(n^2-F(n,n))(m^2-F(m, m))-n^2 m+nF(n,m)+mF(n,n)-\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2\\ \end{aligned} \] 最后 \(\sum_{i=1}^n \lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor i^2\) 这东西可以二维整除分块，两个整除分块叠加，块的数量是相加的。
P4213 【模板】杜教筛（Sum）
见 笔记 杜教筛。
P4318 完全平方数
二分 + 容斥。
先二分答案，然后考虑计算 \(f(n)=\sum_{i=1}^n \mu(i)^2\)。
从另一个角度考虑，\(f(n)\) 让有平方因子的数贡献为 \(0\)，容斥的算就是 \(-\) \(2^2\) 的倍数 \(-\) \(3^2\) 的倍数 \(+\) \(6^2\) 的倍数，根据 \(\mu\) 的定义，容斥系数就是 \(\mu\)，所以 \(f(n)=\sum_{i=1}^{\sqrt{n}}\mu(i)\lfloor\frac{n}{i^2}\rfloor\)。
复杂度 \(\mathcal O(\sqrt{n}\log n)\)。
28日
P4841 [集训队作业2013]城市规划
多项式求逆。
设 \(f(n)\) 表示 \(n\) 个点的无向连通图方案数，\(g(n)\) 表示 \(n\) 个点无向图方案数（即 \(2^{\binom{n}{2}}\)）。
钦定 \(1\) 号点不动，枚举 \(1\) 所在连通块大小，推式子： \[ \begin{aligned} g(n)&=\sum_{i=1}^n \binom{n-1}{i-1}f(i)g(n-i)\\ g(n)&=\sum_{i=1}^n \frac{(n-1)!}{(i-1)!(n-i)!}f(i)g(n-i)\\ \frac{g(n)}{(n-1)!}&=\sum_{i=1}^n \frac{f(i)}{(i-1)!}\frac{g(n-i)}{(n-i)!}\\ \end{aligned} \] 设 \(F(n)=\frac{f(i)}{(i-1)!}\)，\(G(n)=\frac{g(n-i)}{(n-i)!}\)，\(H(n)=\frac{g(n)}{(n-1)!}\)，可以看出来这是个卷积。 \[ H(n)=\sum_{i=1}^nF(i)G(n-i)\Leftrightarrow F=H*G^{-1} \] 我们已知 \(H,G\)，就可以用多项式求逆做。
P4449 于神之怒加强版
整除分块 + 线性筛。
我们知道 \(\mu*I=\epsilon\)，则 \[ \begin{aligned} &\quad\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k\\ &=\sum_{d=1}^n d^k\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}[\gcd(i,j)=1]\\ &=\sum_{d=1}^n d^k\sum_{i=1}^{\lfloor n/d\rfloor}\sum_{j=1}^{\lfloor m/d\rfloor}\sum_{x|i,x|j}\mu(x)\\ &=\sum_{d=1}^n d^k\sum_{x=1}^{\lfloor n/d\rfloor}\mu(x)\lfloor n/dx\rfloor\lfloor m/dx\rfloor\\ &=\sum_{d=1}^n d^k\sum_{y=1}^{\lfloor n\rfloor}\mu(y/d)\lfloor n/y\rfloor\lfloor m/y\rfloor\\ &=\sum_{y=1}^{n}\lfloor n/y\rfloor\lfloor m/y\rfloor\sum_{d|y} d^k\mu(y/d)\\ \end{aligned} \] 设 \(f(n)=\sum_{d|y} d^k\mu(\frac{y}{d})\)，是个积性函数，考虑线性筛。
若 \(n=\prod p^c\)，则 \[ \begin{aligned} f(n)&=\prod(-p^{k(c-1)}+p^{kc})\\ &=\prod p^{k(c-1)}(p^k-1) \end{aligned} \] 这样 \(f\) 就满足了能够快速求得 \(f(p),f(p^k)\)。
复杂度 \(\mathcal O(n\log n+T\sqrt{n})\)。
P3723 [AH2017/HNOI2017]礼物
FFT。
题目让我们求 \[ \begin{aligned} &\quad\sum_{i=1}^n(a_i-b_i+c)^2\\ &=\sum_{i=1}^na_i^2+\sum_{i=1}^nb_i^2+2c\sum_{i=1}^n(a_i-b_i)+nc^2-2\sum_{i=1}^na_ib_i\\ \end{aligned} \] 发现前两项是不变项，和 \(c\) 相关的是二次函数（值域很小大力枚举就好），问题是旋转 \(a\) 序列最大化最后一项。
倍长 \(a\) 就是 \(\sum_{i=1}^{2n} a_{i+k}b_i\)，翻转 \(b\) 得到 \(\sum_{i=1}^{2n} a_{i+k}b_{n-i}\) 是个卷积，FFT 卷后在 \([n+1,2n]\) 上找最大值即可。