虽然第一天是 8.31，但确实是开学第一个月，就一块算进去了。
-
法一：二分答案，将大于等于 \(mid\) 的数设为 \(1\)，小于的设为 \(0\)，最后位置上如果是 \(1\) 说明大于等于 \(mid\)，否则小于，时间复杂度 \(O(n\log n)\)，空间复杂度线性。
法二（待做）：线段树分裂，时间复杂度和空间复杂度均为 \(O(n\log n)\)。
-
CF558E（待做）
操作同上题，要求求出完整序列，关键点在于字符集大小只有 \(26\)。
法一：线段树分裂，同上。
法二：每个字母开一个动态开点权值线段树，修改时求出区间内各字母的数目，做 \(26\) 次区间覆盖。
-
\(S_i=1\) 和 \(T_i=1\) 的部分分非常具有启发意义，对于 \(u\) 点答案的计算，我们考虑一条在 \(t_x\) 时刻从 \(u\) 子树内一点 \(x\) 开始上行到根的路径，对 \(u\) 产生贡献等价于 \(dep_x+t_x=dep_u+w_u\)；类似地，从根下行，到点 \(x\) 的时刻为 \(t_x\)，产生贡献等价于 \(dep_x-t_x=dep_u-w_u\)。
尝试把所有路径转化为一端在根节点，考虑差分，对于路径 \(u\to v\)，记 \(x=\mathrm{LCA}(u,v)\)，将该路径拆为从 \(u\) 到根和从根到 \(v\) 贡献为 \(1\) 的路径以及从 \(x\) 到根和从根到 \(fa_x\) 贡献为 \(-1\) 的路径，于是将所有操作的贡献放到了子树里，树上启发式合并即可，时间复杂度 \(O((n+m)\log n)\)。
-
由于是先序遍历，交换左右子树实际只会影响左右子树交叉部分的贡献，于是答案即为所有左右子树的逆序对（不交换）和顺序对（交换）贡献取最小值再求和，这个操作能够在线段树合并时完成，具体而言，记左右儿子为 \(x,y\)，其在线段树的左右儿子记为 \(ls,rs\)，逆序对为 \(\sum S(x_{rs})S(y_{ls})\)，顺序对为 \(\sum S(x_{ls})S(y_{rs})\)，时间和空间均有复杂度 \(O(n\log n)\)。
-
有解情况下最终的 \(A\) 序列的元素一定为原序列 \(\gcd\) 的因数，枚举这个因数 \(d\)，答案为所有 \(A_i\) 变到 \(d\) 的次数和。记一个 \(f\) 为用 \(B_i\) 组成乘积的最小次数，去掉 \(B\) 中的 \(1\) 并对 \(B\) 去重，能够调和级数处理出这个背包，然后就能过了。
-
毛毛虫实际是一种树，所以先做边双，每个边双的删点次数是边双内节点个数减 \(1\)，然后变成树，一棵树的删点次数是大小减去主路径长减去叶子个数再加 \(1\)，所以主路径要选直径，最后把树连起来还要删个数减 \(1\) 次。
-
要求删边后连通，果断边双出一棵树。考虑下性质，边双内的边随便选，最后乘，先不管；记边双 \(u\) 内节点数为 \(w_u\)，则在一个边双内选点的方案有 \(2^{w_u}-1\) 种。
现在尝试设计一个 DP，\(f_{u,0/1}\) 表示 \(u\) 子树内不选点和选点的方案，选点关系到边 \((fa_u,u)\) 是否需要选、\(u\) 本身是否需要选，等等。由状态内情况过多引起的无法转移通常有两种解决方案，增加状态数和对状态限制，前者是做一个 \(f_{u,0/1/2}\) 表示不选点、选点且子树外选点和选点且子树外不选点，后者强制子树外不选点，且不选边 \((fa_u,u)\)，以保证不重不漏。
采用后者，推转移，初始 \(f_{u,0}=1,f_{u,1}=2^{w_u}-1\)，枚举每个 \(v\to u\)，考虑是否前面的子树中是否已选点，有 \(f_{u,1}\leftarrow f_{u,0}\times f_{v,1}+f_{u,1}\times (2f_{v,0}+f_{v,1})\)，然后转移 \(f_{u,0}\leftarrow f_{u,0}\times 2f_{v,0}\)，统计答案 \(f_{1,1}+\sum\limits_{u=2}^{idx}f_{u,1}\times 2^{idx-siz_u-1}\)，最后乘上边双内随便选的 \(2^{m-idx+1}\)。
-
离线动态图连通性。
法一：线段树分治模板题，把条边在时间轴出现的闭区间离线处理出来，然后用按秩合并的并查集维护连通性。
法二：LCT，同上处理边，对边按出现时间升序排序，扫描时间轴，双指针加边，边的删除时间作为边权，维护一个最大生成树即可。两点 \(x,y\) 在 \(i\) 时刻连通的充要条件是 \(x,y\) 在 LCT 上连通且路径最小边权大于等于 \(i\)。
-
维护位置序列，有青蛙为 \(1\)，否则为 \(0\)，对于询问 \(x\) 寻找的落点实际上是 \(x\) 后方的第一个 \(0\)，可以直接线段树做一个区间 \(\min\) 并记录最小的出现位置。另外一个办法是维护区间 \(1\) 个数，线段树上二分。具体地，记 \(S_i\) 为 \(i\) 的前缀和，询问实际上是找最大的 \(y+1\) 使得 \(S_y-S_x=y-x\)，变形为 \(S_y-y=S_x-x\)，若右子树的左端点满足条件就向右子树走，否则左子树。记一个右子树左端点 \(l\) 的 \(sum=S_{l-1}\)，再用原序列加上 \(l\) 的单点值即可。
-
细节题。避免一直写 \(-1\)，把 \(x_i,y_i\) 整体移一下，以下记作 \(up_i,dn_i\)，且记 \(L_i,H_i\) 表示 \(i\) 位置没有障碍的闭区间。
首先设计状态 \(f_{i,j}\) 表示到 \(i,j\) 时的答案（\(0\le i,j\le m\)），初始化 \(f_{0,i}=0\)，其他置为 \(+ \infty\)，容易得到转移 \(f_{i,j} \leftarrow \min \{ f_{i-1,j-k \cdot up_i}+k,f_{i-1,j+dn_i} \}\)。注意到前项实际上是一个完全背包，因此进行类似的优化，从小到大枚举 \(j\)，有 \(f_{i,j} \leftarrow \min \limits_{up_i+1}^{H_i} \{ f_{i-1,j-up_i}+1,f_{i,j-up_i}+1 \}\)，枚举下界为 \(up_i+1\) 的原因是需要处理完全背包，当然也可以先转移 \(01\) 背包，再转移完全背包，分开写。现特判 \(H_i=m\) 的情况，可以由 \(i-1\) 的任意合法位置转移而来，此时 \(f_{i,m} \leftarrow \min \limits_{j=L_{i-1}}^{H_{i-1}} \left ( f_{i-1,j}+\max\{1,\lceil \frac{m-j}{up_i} \rceil \} \right)\)，对 \(1\) 取 \(\max\) 是考虑由 \(f_{i-1,m}\) 转移而来的情况。由于下行是 \(01\) 背包，且不能同时向上和向下，因此先转移以上式子，再转移下行情况，最后还要将 \(1\le i<L_i\) 的部分置为 \(+\infty\)。