做题记录
ksmgxeh
·
·
个人记录
P1129
二分图匹配。
复习板子。对于 i 行 j 列的点为黑色，就把 i 向 j 连一条边。如果把点看成匹配边的话最后的状态就是每行每列都匹配上了。而交换行和列其实不会改变最大匹配树，只会接近最终的匹配状态。最后如果最大匹配树等于 n 则有解，否则无解。
下面是二分图匹配模板。
bool dfs(int x){
for(int i=1;i<=n;i++){
if(e[x][i] && !vis[i]){
vis[i]=1;
if(!match[i] || dfs(match[i])){
match[i]=x;
return true;
}
}
} return false;
}
P1260
差分约束。
复习板子。看到形如 u-v \le lim 的条件，从 v 向 u 连一条权值为 lim 的边。建完图后图可能不连通，建立 0 号点向所有点连权值为 0 的边。然后跑 spfa，存在负环则无解。判断负环的方法时从队列里取出的点记为 x，让 cnt_x 自增，当 cnt_x=n 时存在负环。
求出所有点中最小的 mindis，答案即为 ans_i = dis_i-mindis。
P1410
dp。
很巧妙的状态设计。设 f_{i,j} 表示当前的上升子序列以 a_i 结尾，长度为 j 时，另一个上升子序列末尾的最小值。初始 f 为无穷大，f_{0,0}=0。
$f_{i-1,i-j}$ 表示将前 $i-1$ 个数划分成 $A,B$，其中 $A$ 以 $a_{i-1}$ 结尾，长度为 $i-j$，$B$ 的结尾为 $f_{i-1,i-j}$。如果 $a_i>f_{i-1,i-j}$，$a_i$ 可以接在 $B$ 后面，$A$ 保持不变，$f_{i,j}=\min(f_{i,j},a_{i-1})$。
判定答案时如果 $f_{n,n/2}$ 没有被更新过，说明无解。
### [P1450](https://www.luogu.com.cn/problem/P1450) ###
多重背包，容斥。
用多重背包跑出价格到 $s$ 时的方案数，然后用容斥算出价格超过硬币限制的情况。
### [P1641](https://www.luogu.com.cn/problem/P1641) ###
组合数学。
将选择 $n$ 个 $1$ 和 $m$ 个 $0$ 的过程看作在一个 $n*m$ 的网格图中从 $(0,0)$ 走到 $(n,m)$，其方案数不难看出是 $\mathrm{C}_{n+m}^{n}$。考虑限制，对应到网格图中也就是不能经过 $y=x$ 这条直线，将网格沿直线翻折，计算不合法的路径数，不难得出为 $\mathrm{C}_{n+m}^{n+1}$。所以答案即为 $\mathrm{C}_{n+m}^{n}-\mathrm{C}_{n+m}^{n+1}$。
### [P1651](https://www.luogu.com.cn/problem/P1651) ###
差值 dp。
融合多种技巧的 dp。询问能堆成的最大的相同高度，考虑以差值记录状态，设 $f_{i,j}$ 为用了前 $i$ 个木块差值为 $j$ 时较高塔的最大高度。有三种转移：不选，$f_{i+1,j} =\max(f_{i+1,j},f_{i,j})$；把木块加到较高塔，$f_{i+1,j+a[i+1]} =\max(f_{i+1,j+a[i+1]},f_{i,j}+a[i+1])$；把木块加到较低塔，$f_{i+1,j-a[i+1}=\max(f_{i+1,j-a[i+1]},f_{i,j})$。最后判断 $f_{n,0}$ 小于等于 $0$ 则无解，否则答案为 $f_{n,0}$。
第一个点是状态第二维有可能出现负数，这里可以用宏定义平移下标解决：第二个点是每次转移只用到上一次的转移，可以用第一维与 $1$ 的滚动数组优化空间。
### [P1841](https://www.luogu.com.cn/problem/P1841) ###
floyd。
枚举中转点 $k$ 时判断是否能更新 $dis$ 数组，如果可以说明这个点一定是重要的城市。还要判断更新前是否已经相等，如果相等说明这个中转点无效，标记即可。**注意不要初始化自己到自己为零**，这样默认有自环，会 wa。
### [P1850](https://www.luogu.com.cn/problem/P1850) ###
期望 dp，floyd。
实际是缝合题。套用期望 dp 的转移公式： $f = (\sum f' \times p) + w$，其中 $f'$ 为下一个状态，$p$ 为转移至这个状态的概率，$w$ 为转移的代价。这题中代价就是两点间的最短路 $dis_{u,v}$。
设 $f_{i,j,0/1}$ 前 $i$ 次课程中已经申请了 $j$ 次，当前申请成功、失败的期望。然后转移方程是一大坨，具体来说就是要分情况讨论当前教室和上一个教室，乘上相应的成功或失败的概率。
### [P1967](https://www.luogu.com.cn/problem/P1967) ###
生成树，lca。
思路很显然，对原图求最大生成树，在树上倍增维护祖先与到祖先的路径中最小的边权。**注意求出的树其实是森林**，即不连通，所以要对每个树跑一次倍增!
### [P2161](https://www.luogu.com.cn/problem/P2161) ###
set 的应用。
把每个线段按右端点从小到大排序。对于每个插入操作，先 upper_bound 找到第一个大于此线段的线段，暴力枚举直到找到一个不满足条件的线段。
遍历 set 可以用 auto 或迭代器。
### [P2195](https://www.luogu.com.cn/problem/P2195) ###
树的直径。
记录一个错误点：当两个连通块用长度为 $1$ 的边合并后求最小的直径时，如果原直径是 $l1,l2$，那么新直径是 $\max(l1,l2,\frac {l1+1}{2}+\frac {l2+1}{2} + 1)$。记得**要和 $l1,l2$ 比较！**
### [P2467](https://www.luogu.com.cn/problem/P2467) ###
dp。
设 $f_{i,j}$ 为选前 $i$ 个数并让 $j$ 作为山峰的方案数。发现波动数组有如下性质：当 $i$ 和 $i-1$ 不相邻时，交换两个数仍然合法；用 $n+1$ 减去长度为 $n$ 的合法序列得到的新序列仍然合法；合法序列反转后仍为合法序列。
由性质 $1$ 首先有 $f_{i,j} = f_{i,j-1}$。然后对于 $j$ 和 $j-1$ 相邻的情况，我们将 $j$ 删去，那么 $j-1$ 成为山谷，此时用 $i$ 减去所有数即可，所以有 $f_{i,j} = f_{i,j-1} + f_{i-1,i-j+1}$。由于每次更新只用到前面的一次，可以用滚动数组优化空间。
答案为 $2 \times \sum_{2 \le i \le n} f_{n,i}$，乘 $2$ 是因为对称性。
### [P2476](https://www.luogu.com.cn/problem/P2476) ###
记忆化搜索。
第一次见是比较难想到的。看到每种颜色能用的数量 $k\le 5$，考虑以此设计状态。设 $f_{a,b,c,d,e,pre}$ 表示还有 $a$ 个还能用 $1$ 次的颜色，$b$ 个还能用 $2$ 次的颜色……$e$ 个还能用 $5$ 次的颜色，上一次用的颜色能用的次数是 $pre$ 的涂色方案。枚举 $5$ 种情况，将当前颜色减 $1$，乘上对应的颜色数量，如果 $pre$ 等于枚举到的颜色，颜色数量要减 $1$，因为用掉这个颜色后，这个颜色会与剩下颜色次数中的颜色相同。
### [P2480](https://www.luogu.com.cn/problem/P2480) ###
数论大杂烩。
给定 $G,n$，求
$$G^{\sum_{d|n} {\tbinom{n}{k}}} \bmod 999911659$$
首先特判 $G=999911659$ 时，所求为 $0$。
$999911659$ 为质数，根据欧拉定理，所求即为
$$G^{\sum_{d|n} {\tbinom{n}{k}} \bmod 999911658} \bmod 999911659$$
因为 $999911658$ 不是质数，不能保证对于所有的 $x$ 都存在逆元，上式无法直接计算。
注意到 $999911658 = 2 \times 3 \times 4679 \times 35617$，即可以分解成 $4$ 个不同的质数，我们可以分别求出 $\sum_{d|n} {\tbinom{n}{k}}$ 在模 $2,3,4679,35617$ 这几个质数下的结果，最后用中国剩余定理合并答案。
也就是说，我们要求下面一个线性方程组的解：
$$ \begin{cases}
x \equiv a_1 \pmod{2} \\
x \equiv a_2 \pmod{3} \\
x \equiv a_3 \pmod{4679} \\
x \equiv a_4 \pmod{35617}
\end{cases}
$$
而计算小组合数对小质数取模的结果，可以用卢卡斯定理快速计算。
### [P2515](https://www.luogu.com.cn/problem/P2515) ###
强联通分量，树上背包。
有依赖关系的选择想到背包。但是**有可能存在环**，即不同点之间相互依赖，这时候可以用缩点把这个强连通分量的价值和重量加在一起，再在这棵树上做背包。
下面是树上背包模板。
```cpp
void dfs(int x){
for(int i=W[x];i<=m;i++) dp[x][i]=V[x];
for(int i=0;i<a[x].size();i++){
int y=a[x][i];
dfs(y);
for(int j=m;j>=W[x];j--)
for(int k=0;k<=j-W[x];k++)
dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[y][k]);
}
}
```
### [P2573](https://www.luogu.com.cn/problem/P2573) ###
生成树。
注意到最终形成的路径其实是原图的 $1$ 棵生成树。从 $1$ 号点 dfs 找到所有能到的点，把每条边按高度排序，求最小生成树。
### [P2607](https://www.luogu.com.cn/problem/P2607) ###
树形 dp。
注意到有 $n$ 个点，一共只有 $n$ 条边，那么最终形成的要么是 $1$ 棵基环树，要么是多个圈。
如果最终形成的是 $1$ 棵树，那么可以借鉴没有上司的舞会做法，设 $dp_{i,0/1}$ 为当前点选或不选获得的最大价值。我们将环的任意一条边断掉，对边的两端点分别做一次树形 dp，那么这个连通块的答案就是 $ans = \max(dp_{s1,0},dp_{s2,0})$。
最后可能形成多个连通块，对每个连通块求一次答案 $\sum {ans}$。
### [P2757](https://www.luogu.com.cn/problem/P2757) ###
据说是很典的 trick。
转化为判断是否存在一个长度为 $3$ 的等差数列。因为有排列这个强条件，枚举等差中项 $a_i$ 则可发现如果公差为 $k$，当且仅当 $a_i-k$ 与 $a_i+k$ 分别位于 $a_i$ 两侧时合法。
动态维护存在性 $01$ 序列，看看有哪些数字已经在左边出现过，如果这个序列是回文序列，说明加减公差后的数值都在这个中点的一端，因此无解。反之则有解。
判断回文？上 hash。动态更新 hash？上线段树。
### [P2829](https://www.luogu.com.cn/problem/P2829) ###
最短路。
复习次短路写法。如下：
```cpp
memset(dis1,0x3f,sizeof dis1);
memset(dis2,0x3f,sizeof dis2);
q.push({0,1}),dis1[1]=0;
while(!q.empty()){
int x=q.top().second,d=q.top().first; q.pop();
if(dis1[x]!=d && dis2[x]!=d) continue;
for(auto i : e[x]){
int y=i.first,w=i.second;
if(y!=1 && y!=n && deg[y]<k) continue;
if(dis1[y]>d+w){
dis2[y]=dis1[y],dis1[y]=d+w;
q.push({dis1[y],y});
}else if(dis1[y]<d+w && dis2[y]>d+w){
dis2[y]=d+w;
q.push({dis2[y],y});
}
}
}
cout<<(dis2[n]==inf ? -1 : dis2[n]);
```
这道题毒瘤的地方在于存在重边和自环，相信正赛中不会出现此类。
### [P2831](https://www.luogu.com.cn/problem/P2831) ###
状压 dp。
预处理出每条抛物线能攻击到的小猪有哪些，记此集合为 $s$。设 $f_S$ 表示当前状态为 $S$ 时花费的最小代价。转移有两种情况：
枚举每条抛物线，$f_{S|s_i} = \max(f_{S|s_i},f_S + 1)$。
枚举每个点，$f_{S|(1<<i-1)} = \max(f_{S|(1<<i-1)},f_S + 1)$。
注意初始化 $f_0 = 0$，答案即为 $f_{1<<(n-1)}$。
### [P3066](https://www.luogu.com.cn/problem/P3066) ###
dfs 序，双指针。
将所有点按深度排序后，从大到小遍历每个点。用一个指针指向与当前节点距离大于 $t$ 的点，用树状数组消除这个点的贡献。用 dfs 序统计一个点子树内的所有贡献。
### [P3067](https://www.luogu.com.cn/problem/P3067) ###
折半搜索。
将原数组分成两半，想象把目标子集分成两组和相同的数，设在前一半放入第一组的数为 $a$，放入第二组的数为 $b$，在后一半放入第一组的数为 $c$，放入第二组的数为 $d$，即要求 $a+c=b+d$。把在同一边的放在一起，转换成 $a-b=d-c$，所以搜到每个数时有三种选择：跳过，加上这个数，减去这个数。后两种情况用一个状态数组记录一下，在第二次搜索中判断第一次搜索中这个和是否出现过，把两次状态并起来最后枚举一遍就行了。
### [P3069](https://www.luogu.com.cn/problem/P3069) ###
双指针。
选出 $k$ 种颜色的牛删掉，询问最大连续颜色数？第一次做时我纠结于不知如何处理删除和记录的操作，其实转换成对于拥有 $k+1$ 种颜色的区间中询问最大连续颜色数就很好做。
具体来说，先对每种颜色离散化。用双指针扫一遍区间（左端点不动，右端点扩展），
记录当前区间的颜色种类数 $type$ 和各颜色的最大连续出现数。当 $type > k+1$ 时就固定右端点，移动左端点直至满足条件。
### [P3155](https://www.luogu.com.cn/problem/P3155) ###
树形 dp。
设 $f_{i,j}$ 表示第 $i$ 个点染成颜色为 $j$ 的最小代价。初始化所有节点 $f_{i,0} = f_{i,1} = 1$，特别地，当 $i$ 为叶子节点时，$f_{i,!c_i}$ 为无穷大，即保证叶子节点不会被染成其他颜色，因此不能转移。考虑一个1节点可以继承它父亲的颜色，所以有两种情况：继承父亲的颜色，或染成与父亲不同的颜色。不难得出转移方程为：
$$ f_{fa,1} = f_{fa,1} + \min(f_{x,1}-1,f_{x,0}) \\
f_{fa,0} = f_{fa,0} + \min(f_{x,0}-1,f_{x,1})
$$
### [P3177](https://www.luogu.com.cn/problem/P3177) ###
树形 dp。
好题。将收益之和转换成**每条边权对答案的贡献**。设 $ dp_{i,j}$ 表示以 $i$ 为根节点，子树内选了 $j$ 个黑色节点的最大收益。答案为 $dp_{1,m}$。
记录以 $u$ 为根的子树大小 $siz_u$。枚举当前黑节点数 $j$，和其儿子 $v$ 子树内黑节点数 $k$，计算这条边权 $w$ 分别被白点和黑点走过的贡献。类似树上背包，一定要**倒序枚举** $j$，**正序枚举** $k$，否则一个状态可能会重复计算。转移方程如下：
$$ dp_{u,j} = \max(dp_{u,j},dp_{u,j-k}+dp_{j,k}+w\times k\times (m-k)+w\times (siz_v-k)\times (n-m-siz_v+k) $$
### [P3203](https://www.luogu.com.cn/problem/P3203) ###
分块。
分块大法好。注意到操作是连续的，我们把 $n$ 个点分成 $\sqrt{n}$ 块，维护从 $i$ 开始跳跳出当前块的步数，以及跳出当前块到达的位置。对于修改操作，把修改点所在块暴力修改。
### [P3228](https://www.luogu.com.cn/problem/P3228) ###
组合数学。
对于原序列 $a_1,\dots,a_k$，当 $a_k \le n$ 时会造成 $1$ 的贡献，由于 $a_1$ 的取值不同，所有情况最后总共会造成 $n-a_k$ 的贡献。
考虑其**差分序列** $s_i = a_{i+1}-a_i$，要求 $1\le s_i\le m$，那么此时 $a_1$ 的值可以任取，对于不同的差分序列最后会造成 $n-\sum_{i=1}^{k-1} s_i$ 的贡献。
差分序列的每一项有 $m$ 种选择，所以总共有 $m^{k-1}$ 种差分序列。那么答案为 $\sum_{i=1}^{m^{k-1}} (n-\sum_{j=1}^{k-1} s_{i,j})$，将 $n$ 提到外面变为 $n \times m^{k-1} - \sum_{i=1}^{m^{k-1}}\sum_{j=1}^{k-1} s_{i,j}$。
由限定条件 $M \times (K-1) < N $，所以长度为 $k-1$ 的序列中 $1$ 到 $m$ 的个数都被**平均的取到**。每个数取到的次数即为 $\frac{m^{k-1}(k-1)}{m} = m^{k-2}(k-1)$，使用求和公式那么后面的一大坨就是 $\frac{m^{k-1}(k-1)(m+1)}{2}$。答案即为：
$$
n\times m^{k-1}-\frac {m^{k-1}\times (k-1)\times (m+1)} {2}
$$
注意 $n\le 10^{18}$，所以在所有乘 $n$ 的地方都要取模。
### [P3243](https://www.luogu.com.cn/problem/P3243) ###
拓扑排序。
观察得到最优解的排列为反序列字典序最大的序列。那么对原图建其反图跑拓扑排序，要求字典序最大，用大根堆代替普通队列。无解即判断是否有环，看最后遍历点数是否小于原图点数即可。
### [P3457](https://www.luogu.com.cn/problem/P3457) ###
并查集。
把每个点按高度从小到大排序，访问每个点，如果相邻点高度大于当前点，让相邻点作为父亲。最后数一遍有多次没能成功覆盖，即为需要添加的抽水机数目。注意不能让枚举点当父亲，因为此时可能相邻点还未访问过。
### [P3537](https://www.luogu.com.cn/problem/P3537) ###
trick 题
对于条件 $1$，排序即可满足，对询问离线。对于条件 $2$，容易想到用背包来做。令 $f_S$ 表示选到和为 $S$ 的物品时，最小的 $b_i$ 最大是多少，这样就能满足尽可能多的限制。
### [P3539](https://www.luogu.com.cn/problem/P3539) ###
贪心。
预处理所有斐波那契数。每次二分在数列中找到第一个大于等于当前 $x$ 的数 $f_i$，取 $\min = (f_i-x,x-f_{i-1})$ 为下一个数，直至变为 $0$。可以证明这样时最优的，复杂度为 $\log$ 级别。
### [P3567](https://www.luogu.com.cn/problem/P3567) ###
二进制拆分。
看到题后感觉要上主席树，但总感觉有点大材小用。一翻题解果然找到了一个新做法，很妙，遂记之。
题目要求询问一段区间内是否有数的出现次数严格大于区间长度的一半。当用二进制表示时，我们发现答案的二进制表示中 $1$ 的个数也一定超过一半，累加即可。但有可能会凭空创造 $1$ 个新数，二分特判即可。
### [P3572](https://www.luogu.com.cn/problem/P3572) ###
单调队列优化 dp。
做的时候感觉一直在处理细节，从 $1$ 开始还是从 $2$ 开始，先更新队尾还是队首，一直在往之前做过的模板上套。最后想通了，题目的处理方法不是一成不变的，千万不要想着之前是怎么做的，关键是掌握算法的思想，**具体情况具体分析**。这题方便的写法就是先更新队首。
### [P3591](https://www.luogu.com.cn/problem/P3591) ###
倍增，根号分治。
首先根据数据范围不难想到与根号算法有关。看每一次跳的步数，如果步数为 $1$，可以直接预处理深度 $O(1)$ 计算。这启示我们对于步数较小的情况使用预处理的结果，而步数较大的情况倍增暴力计算。设这个步数阈值为 $B$。
预处理 $val_{u,k}$ 表示 $u$ 跳 $k$ 步向上获得的之和，即 $\sum_{v \in \mathrm{ancestor(u)}} a_v \times [k\mid (dep_u - dep_v)]$。
总时间复杂度 $O(nB + \frac {n^2}{B} \log n)$，当 $B$ 取 $20$ 时最优。
注意处理路径上节点的时候细节很多。
### [P3599](https://www.luogu.com.cn/problem/P3599) ###
数论，构造。
构造好题。
首先是前缀和部分。不难发现 $a_1$ 必须为 $n$，否则存在 $1 < i < n$ 满足 $a_i \equiv a_{i+1} \pmod n$。并且 $n \in even \cup \{1\}$，否则有：
$$ \sum_{i=1}^{n-1} = \frac {n \times (n-1)} {2} \equiv a_1 \pmod n $$
这是判断是否合法，接下来考虑如何构造。
通过**暴力搜索**找到一种构造方法：当 $i \in odd$，$a_i = n+1-i$；当 $i \in even$，$a_i = i-1$。下面用 $n=6$ 举例并证明。
此时得到的排列为 $6\;1\;4\;3\;2\;5$，模 $n$ 意义下变为 $0\;1\;-2\;3\;-4\;5$。求其前缀和发现：当 $i \in odd$，$sum_i = \{0,-1,-2\}$；当 $i \in even$，$sum_i = \{1,2,3\}$。还原成正数得到 $\{1,2,3,4,5,6\}$。推广到更大的数也必然成立。
再看前缀积部分。不难发现 $a_1$ 必须为 $1$，$a_n$ 必须为 $n$。并且 $n$ 必须为质数或 $1$ 或 $4$。因为当 $n$ 为合数时存在 $p<q<n$ 使得 $pq \equiv 0\pmod n$。至于 $1$ 和 $4$ 是特殊情况。
发现整数时的序列是不好构造的，不妨推广到有理数上。发现只需构造形如 $1,\frac{2}{1},\frac{3}{2} ,\cdots,\frac{n}{n-1}$ 的序列，这样其前缀积自然是 $1$ 到 $n$ 的排列。将其转换成整数，用逆元可以处理。又因为 $n$ 为质数，可以用费马小定理求解。最后求得的数是 $0$ 到 $n-1$ 所有数在模 $n$ 意义下的逆元加 $1$，自然构成 $1$ 到 $n$ 的排列。
### [P3629](https://www.luogu.com.cn/problem/P3629) ###
树的直径。
具体思路就不写了，主要就是用了两种求树的直径的方法。
第一种是两遍 dfs，适用于求出具体路径，不适用于存在负权的树，注意在第 $2$ 遍 dfs 时再用 pre 记录路径。
```cpp
void dfs1(int x,int fa,int dis,int &s,int t){
if(l1<dis) l1=dis,s=x;
if(t==2) pre[x]=fa; //第二遍时才能记录直径
for(int i=0;i<e[x].size();i++){
int y=e[x][i];
if(y==fa) continue;
dfs1(y,x,dis+1,s,t);
}
}
int main()
{
dfs1(1,0,0,s,1); //第一遍
l1=0;
dfs1(s,0,0,t,2); //第二遍
}
```
第二种是 dp。适用于存在负权的情况，不能记录路径。
```cpp
void dfs2(int x,int fa){
for(int i=0;i<e[x].size();i++){
int y=e[x][i],w=1;
if(y==fa) continue;
dfs2(y,x);
if(vis[x] && vis[y]) w=-1;//这一行是题目中要求的操作，模板中不需要。
l2=max(l2,dp[x]+dp[y]+w);
dp[x]=max(dp[x],dp[y]+w);
}
}
```
### [P3740](https://www.luogu.com.cn/problem/P3740) ###
线段树。
因为颜色覆盖是有顺序的，如果倒着看，不拿发现靠后的颜色一定不会被覆盖掉。那么只需从后往前进行区间修改，每次判断是否有空间添加新的颜色。**注意要把区间左右端点的邻位也进行离散化**。
### [P3959](https://www.luogu.com.cn/problem/P3959) ###
状压 dp。
设 $f_{S,i,j}$ 表示打通点的状态为 $S$，且 $i$ 的深度为 $j$ 时的最小代价。
转移方程为：
$$ f_{S,i,j} = \min_{(i,k,w) \in E \land k \in T \subset S} f_{T-k,k,j+1} + f_{S-T,i,j} + j \times w$$
最后答案为：
$$ ans = \min_{i=1}^{n} f_{all-i,i,1}$$
转移的过程可以用记忆化搜索实现。
### [P4042](https://www.luogu.com.cn/problem/P4042) ###
dijkstra 的应用。
记 $dp_i$ 为消灭第 $i$ 个怪物的代价，直接跑 dp 会有后效性。
较为常见取消后效性的方法是按某个值排序，这道题中按 dp 值排序。
dp 的转移式为：$dp_i = \min(K_i,S_i+ \sum_{j=1}^{R_i} dp_{v_j})$。
所以 $dp_i$ 能被更新当且仅当对任意的 $dp_{v_j}$ 都有 $dp_{v_j} < dp_i$。
于是我们对 dp 值建一个小根堆，令每个点初始值为 $K_i$，每次弹出一个 dp 值更新其他 dp 值。如果被更新的 dp 值已更新完，再把它加入到堆中。
### [P4188](https://www.luogu.com.cn/problem/P4188) ###
差分，离散化。
有 $n$ 个线段，询问去掉其中一段后，其他线段覆盖的总长度最大为多少。
考虑只移走 $1$ 条线段带来的影响，即原来只覆盖一次的区间不会再被覆盖。用前缀和记录从 $1$ 到 $i$ 恰好被覆盖 $1$ 次的线段数 $C_i$。那么从 $a$ 到 $b$ 覆盖了 $1$ 层的线段数就是 $C_b - C_{a-1}$。
### [P4308](https://www.luogu.com.cn/problem/P4308) ###
倍增，floyd。
利用好数据范围可以很好地猜出算法。设 $f_{i,j,k}$ 表示从 $j$ 到 $k$ 的路径走 $2^i$ 步后得到的最大分数。转移方程也很好列 $f_{i,j,k}=\max(f_{i,j,k},f_{i-1,j,a}+f_{i-1,a,k}*\rho^{2^{i-1}})$，其中 $a$ 为枚举的中转点。最后答案为 $\max{f_{i,s,t}+w_s}$，其中 $s$ 为给定的起点。
### [P4416](https://www.luogu.com.cn/problem/P4116) ###
树剖。
对每个重链的链顶维护一个 set，存储黑色点的编号，查询时顺着往上跳就行。
### [P4503](https://www.luogu.com.cn/problem/P4503) ###
哈希。
找一对仅有 $1$ 个失配位的两个字符串，对于字符串的每一位，我们都用 map 记录原字符串消去这一位后的 hash 值，然后遍历 map，把 $ans$ 加上 $map_i \times (map_i-1)/2$。
### [P4513](https://www.luogu.com.cn/problem/P4513) ###
线段树。
经典题，线段树维护区间最大子段和。
维护四个值：区间总和 $tot$，包含左端点的最大和 $lsum$，包含右端点的最大和 $rsum$，区间最大子段和 $sum$。关键是 pushup 的操作：
$$
t_{p,tot}=t_{ls,tot}+t_{rs,tot} \\
t_{p,lsum}=\max(t_{ls,lsum},t_{ls,tot}+t_{rs,lsum}
) \\
t_{p,rsum}=\max(t_{rs,rsum},t_{rs,tot}+t_{ls,rsum}) \\
t_{p,sum}=\max(t_{ls,rsum}+t_{rs,lsum},t_{ls,sum},t_{rs,sum})
$$
查询时也要注意区间有可能是几个不完整的区间合并在一起，所以返回的是一个结构体，存储 $tot,lsum,rsum,sum$。分四种情况讨论：完全包含，在左边，在右边，跨过中点。最后一种需要把两侧的结构体用上面的方法合并成一个结构体。
### [P5101](https://www.luogu.com.cn/problem/P5101) ###
贪心。
看完题一点思路都没有，全靠看题解理解的。这里写下自己的理解。
首先看到染成其他颜色的代价为当前线段的厚度，那么我们可以在初始厚度为 $1$ 时就染色，这样一定不劣。
然后有一个关键的结论：染色之后绳长可以缩短至 $2$ 的充分必要条件是：除了首尾两段，其余的**同色连续段**的长度都为偶数。（这个证明自己还是不太理解）
用桶动态记录每个颜色出现次数，出现次数的最大值。枚举每个颜色 $col$。则 $ans_{col} = \min(ans_{col},n-cnt_{col}-\max_{col})$。其中 $cnt_{col}$ 为当前颜色的出现次数，$max_{col}$ 为除去两两分段已处理好的 $col$ 段外最大的颜色出现次数。
### [P5283](https://www.luogu.com.cn/problem/P5283) ###
字典树，堆。
首先区间异或和转换为端点的前缀异或和 $s_r\; xor \;s_{l-1}$，发现这是个三角求值，由于 $a \; xor\; b =b\; xor \; a$，补全三角形可转换为一个矩形。所以求前 $2k$ 大的值的和，最后再除以 $2$ 就行了。
将 $n+1$ 个前缀异或和（$s_0$ 也要插入）插入到字典树中。对每个 $i$ 求出第 $t$ 大的 $s_i \; xor \; s_j$，把结果扔到堆里。每次取堆顶，再把 $i$ 对应的第 $t+1$ 大的扔进堆里，重复 $2k$ 次。
### [P5505](https://www.luogu.com.cn/problem/P5505) ###
容斥板子。
很重要。从这道题还了解到了 $TwelveFold Way$ 问题，可以看看[这篇文章](https://www.cnblogs.com/wyxdrqc/p/11696242.html)。
回到这道模板题，其本质是 $ULB$ 问题。考虑到当前第 $i$ 个物品，有 $a_i$ 个，且允许有 $x$ 个空盒，根据容斥原理，最后答案为：
$$ ans = \sum_{i=0}^{n-1} {(-1)^i \dbinom{n}{i} \prod_{j=1}^m \dbinom{a_j+n-1-x}{n-1-x}} $$
### [P5550](https://www.luogu.com.cn/problem/P5550) ###
矩阵乘法。
其实理解清楚矩阵乘法的实质后还是很简单的。注意边界条件和细节：初始矩阵下标还是从 $1$ 开始比较方便，然后转移矩阵记得在纸上多推几遍。
### [P5665](https://www.luogu.com.cn/problem/P5665) ###
单调队列优化 dp。
由于划分出来的每段具有单调性，根据 $a^2 + b^2\le (a+b)^2$ 不难得出最后一段的长度越小越好，也就是划分的总段数越多越好。
于是我们设 $f_i$ 表示前 $i$ 个数的答案，$g_i$ 表示最后一段划分的和。这样只需要每次找到最大的 $j$ 满足 $sum_{j+1,i}≥g_j$ 进行转移即可。即 $pre_i≥g_j+pre_j$，相同变量在一侧，单调队列即可。注意 $g_i$ 不一定大于 $g_{i−1}$，只是要求大于前一段并不是大于上一个位置，所以转移时队列长度至少为 $2$。
需要高精度和卡常。
### [P5569](https://www.luogu.com.cn/problem/P5569) ###
GarsiaWachs 算法。
据说是专门用来解决石子合并问题的算法，是基于最优二叉树提出的。下面只给出算法过程，不给出证明。
一共 $n$ 堆石子，我们要对其进行 $n-1$ 次合并操作。对于每次操作，从左往右找到第一个 $p$ 使得 $a_p<a_{p+2}$，记本次操作合并的代价为 $t = a_p+a_{p+1}$。删除 $a_p$ 和 $a_{p+1}$，从第 $p-1$ 个位置开始往左找到第一个 $q$ 使得 $a_q > t$，并将 $t$ 插入到第 $q+1$ 个位置。
用 vector 实现插入和删除操作，时间复杂度不超过 $O(n\log n)$。
### [P5679](https://www.luogu.com.cn/problem/P5679) ###
算是 bitset 的板子？
枚举中间项，则对于 $i<j<k$，有 $a_k-a_j=a_j-a_i$，转化为 $a_k=2a_j-a_i$。设值域为 $C$，为防止出现负数，变为 $a_k+C=2a_j+C-a_i$。
用 bitset 维护每一个数字的出现情况。用一个 bitset 记录 $C-a_i$，再用一个记录 $2a_j-a_i$。求 $2a_j−a_i$ 的 bitset 只需要将前一个 bitset 左移 $2a_j$ 位即可，如果能在第二个 bitset 内找到 $a_k$，答案为 YES，否则为 NO。
### [P5789](https://www.luogu.com.cn/problem/P5789) ###
矩阵乘法。
对于邻接矩阵 $A$ 的幂的次方，$A^k$ 记录两点 $u$ 到 $v$ 恰好经过 $k$ 条边的路径数。所以题目中的三种情况，都可以用转移矩阵 $E$ 表示出来。停在原地：对于任意的 $u$，$E_{u,u}=1$。去相邻的城市：按照读入的无向图连边，$E_{u,v}=E_{v,u}=1$。自爆：所有点向 $0$ 号点连一条单向边。
### [P6142](https://www.luogu.com.cn/problem/P6142) ###
二分，multiset。
题意很简单，把树划分成若干条链，求最短链长度的最大值。
这种问法肯定是要二分答案，难点在于如何判断最短长度为 $mid$ 时是否合法。这里用 multiset 维护，它的删增操作都是 $\log$ 级别的。对于以 $u$ 为根的子树，维护一个儿子 $v$ 能往上传的链的长度。我们尽量找两条链 $l1,l2$ 使得 $l1+l2$ 尽量接近 $mid$。这里使用二分加双指针完成判断操作。
下面是判断合法的部分。
```cpp
void dfs(int x,int fa){
if(!flag) return;
for(auto y:e[x]){
if(y==fa) continue;
dfs(y,x);
}
multiset<int> s;
for(auto y:e[x]){
if(y==fa) continue;
s.insert(len[y]);
}
if(s.size()%2==0) s.insert(0);
for(auto it=s.begin();it!=s.end();){
auto it2=s.lower_bound(k-*it);
if(it2==it) it2++;
if(it2==s.end()){
it++;
continue;
}
s.erase(it2);
it=s.erase(it); //删掉当前的it后，迭代器指向下一个位置
}
if(s.size()==1) len[x]=*s.begin()+1;
else flag=0;
}
int cal(){
int l=1,r=n;
while(l<r){
for(int i=1;i<=n;i++) len[i]=0;
int mid=l+r+1>>1;
k=mid,flag=1;
dfs(1,0);
if(!flag) r=mid-1;
else l=mid;
}
return l;
}
```
### [P6374](https://www.luogu.com.cn/problem/P6374) ###
倍增，lca。
模拟赛时因为判断情况时太复杂没做出来，思路完全正确。
标程中**结合 dfn 序**判断一个点是否在另一个点的子树内，以及倍增至一个点的子节点的方法大大简化了判断条件。
### [P7251](https://www.luogu.com.cn/problem/P7251) ###
强连通分量。
tarjan 求出原图中的强连通分量后，处理两个问题：
第一问。在给定的图中，最多能选出多少个点，使得这些点在原图中两两可达？答案是最大的强连通分量大小。
第二问。在给定的图中，最少增加多少条边，可以使得这个图变成强连通图？枚举每个强连通分量，记其没有入边的强连通分量个数为 $in$，没有出边的个数为 $out$，答案是 $\max(in,out)$。
### [P7986](https://www.luogu.com.cn/problem/P7986) ###
期望。
为什么用期望？因为选择一个数后将会产生很多会被跳过的数，对它们分类讨论可做，但是细节较多，很难做到不重不漏。本题用期望实现会十分优雅。
设 $dp_{j,k,pre}$ 表示上一个选择了 $pre$（用 $0$ 表示`LO`或连什么都无法产生贡献的东西，$1$ 表示`HI`），当前选择时能选择 $j$ 个`LO`，$k$ 个`HI`时，产生`HILO`个数的期望对 $10^9+7$ 分数取模的结果。
我们倒推，考虑当前选择的值从下一次选择的值转移过来。显然，当前我们有 $j+k$ 种选法（一次可以选一个较大或较小的数询问，使得后面某些数可以跳过，可以视作一次选择了多个连续的`HI`或`LO`）。
对于 $pre = 0$：
$$ dp_{j,k,0} = \frac{1}{j+k} \times (\sum_{x=0}^{j-1} dp_{x,k,0} + \sum_{x=0}^{k-1} dp_{j,x,1} )$$
对于 $pre = 1$：
$$ dp_{j,k,1} =\frac{j}{j+k} + \frac{1}{j+k} \times (\sum_{x=0}^{j-1} dp_{x,k,0} + \sum_{x=0}^{k-1} dp_{j,x,1} )$$
初始 $dp_{0,0,0}=dp_{0,0,1} = 0$，答案为 $dp_{x,n-x,0} \times n!$。
### [P8110](https://www.luogu.com.cn/problem/P8110) ###
推式子。
因为 $A_{ij} = a_i \times b_j$，先考虑 $B = A \times A$，则
$$B_{ij} = \sum_{x=1}^n A_{ix}A_{xj} = \sum_{x=1}^na_ia_xb_xb_j = a_ib_j \sum_{x=1}^na_xb_x = A_{ij}\sum_{x=1}^na_xb_x$$
这说明矩阵 $k$ 次幂相当于给每一项乘上 $\sum_{x=1}^na_xb_x$。
另一方面
$$\sum_{i=1}^n \sum_{j=1}^n A_{ij} = \sum_{i=1}^n \sum_{j=1}^n a_ib_j = (\sum
_{i=1}^n a_i)( \sum_{j=1}^n b_j)$$
所以答案为
$$(\sum
_{i=1}^n a_i)( \sum_{j=1}^n b_j)(\sum_{x=1}^na_xb_x)^{k-1}$$
### [P8756](https://www.luogu.com.cn/problem/P8756) ###
状压 dp。
给定一个棋子的攻击范围，询问在 $n\times m$ 的棋盘上摆放 $k$ 个棋子有多少种互不攻击的方案。
对于这类经典问题，首先看 $n,m$ 的范围，选择小的那一个进行行或列的预处理，目的是先找到保证这一条的互不攻击的状态，以及对应的棋子数量。
然后确定状态设计。设 $f_{i,j,k,l}$ 表示第 $i$ 列的状态为 $j$，前一行的状态为 $k$，此时已经摆放了 $l$ 个棋子的合法方案数。因为本题列的范围更大，所以将其放在状态中。
再根据攻击范围进行枚举，本题棋子可以攻击 $2$ 行内的棋子，于是就有 $5$ 层循环，分别是当前列数，本行状态，已用的棋子数，前前行状态，前行状态。用位运算进行攻击判定，合法时累加转移。完成后枚举最后两列的状态，它们的方案数之和为答案。
### [P8816](https://www.luogu.com.cn/problem/P8816) ###
线性 dp。
把每个点按坐标上的相对顺序排序，然后把添加点数的枚举放在枚举两个点之间，如果之间的空缺超过了能够添加的点数就跳过。设 $f_{i,j}$ 表示前 $i$ 个点添加了 $j$ 个点后的最大答案，则 $f_{i,j} = \max(f_{i,j},f_{t,j+d}+d+1)$，其中 $t$ 为坐标顺序在 $i$ 之前的点，$d$ 为两点间的距离。答案为 $\max_{1 \le i\le n,1\le j\le k} f_{i,j}+j$。
### [P8819](https://www.luogu.com.cn/problem/P8819) ###
和哈希。
题目中判断的两个条件：所有点出度为 $1$，从任意点出发都可以走到一个环上。因为所有点出度为 $1$，所以一条路径可以一直走下去。只需维护条件 $1$ 即可。
将每个点随机赋权，动态维护每个点作为入点时它所连的所有边权和，可以做到 $O(1)$。利用哈希的随机性，判定时构造一个必要不充分条件，但这个“不充分”实际上有非常大非常大的概率充分，以至于不充分性可以忽略不计，从而达到充要判定的效果。
### [P8842](https://www.luogu.com.cn/problem/P8842) ###
考察异或的性质。
要求 $x \oplus y = p$，$p$ 为质数，且 $y < x$，转换为 $x \oplus p = y$。现在想知道有哪些 $p$ 能使异或操作后小于 $x$。对每一位考虑，要想值变小，那么当前位必须相同，即如果第 $i$ 位为 $1$，算出 $2^{i} \sim 2^{i+1}-1$ 中有多少质数累加即可。用前缀和统计。
### [P8844](https://www.luogu.com.cn/problem/P8844) ###
dfs 序，树状数组。
看了题解，主要在每次清空如何处理时感到困惑。给出的方法是将操作离线，因为每次询问只与最近一次修改有关。将修改操作的深度降序排序，在与之对应的查询操作前，把对应深度的点单点加，查询子树时用区间和。
单点加和子树和用树状数组结合 dfs 序实现，每个点最多添加 $1$ 次。时间复杂度 $O(n\log n)$。
### [P9032](https://www.luogu.com.cn/problem/P9032) ###
dp。
考虑枚举公因数计算贡献。设 $dp_{i,j}$ 表示从 $a_{i-dp_{i,j}}$ 到 $a_i$ 全为 $j$ 的倍数的最大长度。预处理 $a_i$ 的所有因数，枚举 $a_i$ 以及其因数，对每一个因数记录一个更新时间戳，当再一次遇到此因数时判断 $tag_j$ 是否等于 $i-1$，如果等于 $dp_{i,j}=dp_{i-1,j}+1$，否则 $dp_{i,j}=1$。当 $k \le dp_{i,j}$ 时，更新 $ans=\max(ans,j\times (sum_i-sum_{i-dp_{i,j}}))$。时间复杂度 $O(n)$。
### [P9233](https://www.luogu.com.cn/problem/P9233) ###
树上启发式合并。
板子题。唯一的思维量是判断子树内所有出现过的颜色出现次数相同转换成当前根节点的颜色出现次数乘上出现次数的出现次数等于子树大小。
启发式合并时统计出现次数的桶和其他计数器一定是建立在整颗树上的，千万不要对每一个子树根节点开一个桶。
### [P9428](https://www.luogu.com.cn/problem/P9428) ###
期望 dp。
跳板有可能失效，所以从上往下遍历避免后效性。对每个点分别记录起点为 $i$ 的时间期望以及其失败概率。
### [P9869](https://www.luogu.com.cn/problem/P9869) ###
并查集。
很容易想到并查集做法，但是细节很多，需要一定的技巧。
首先明确最后的判定条件为一个点找到的父亲为`U`。对于每次赋值，如果是`T`，`F`和`U`，就直接把父亲赋值成对应的值；如果是`+`和`-`，把两个点的父亲赋值。
查找时可能会查到负数下标，所以要取反后再查。又因为可能会陷入 $x$ 到 $-x$ 到 $x$ 的死循环，所以开一个数组记录当前是否到达过。下标又可能为负，同时平移就行了。
询问次数变量不要设成 $T$！因为这里 $T$ 是赋值元素。
### [P10463](https://www.luogu.com.cn/problem/P10463) ###
线段树，gcd。
考虑求解两个数 gcd 的辗转相减法，可以类似地将求区间 gcd 转换为在原数组的差分数组上求 gcd。具体而言，对于区间加转换为单点加，而区间 gcd 即为 $\gcd(a_l,\dots,a_r) = \gcd(a_l,a_{l+1}-a_l,\dots,a_r-a_{r-1})$，只用维护差分数组上的 gcd 和区间和就可以查询和修改了。注意区间加操作时特判 $r=n$ 时不用操作。
### [P10502](https://www.luogu.com.cn/problem/P10502) ###
矩阵乘法。
其实知道矩阵分块法就很好做。我们要求 $S_k = \sum_{i=1}^k A^i$，不妨构造一个 $N\times 2N$ 的矩阵 $F_1 = \begin{bmatrix} A_1 \; S_1 \end{bmatrix}$，以及一个转移矩阵 $T = \begin{bmatrix} A \; A \\ 0 \; E\end{bmatrix}$。其中 $A_n$ 表示题目所给矩阵 $A$ 的 $n$ 次幂，$E$ 为单位矩阵。我们发现 $F_n \times T = \begin{bmatrix} A_{n+1} \; S_{n+1}\end{bmatrix}$。所以最后答案为 $F_k = F_1 \times T^{k-1}$，取后面的 $S_k$ 就行了。用矩阵快速幂计算。
### [P10962](https://www.luogu.com.cn/problem/P10962) ###
换根 dp。
挺板的。或许是太久没碰了，没做出来，要反思。
其实就是维护一个子树内最大值和次大值，然后按正常求树的直径的方法做换根就行了。
### [P10978](https://www.luogu.com.cn/problem/P10978) ###
单调队列优化 dp。
设 $f_{i,j}$ 表示前 $i$ 个工人刷前 $j$ 块木板的最大总价值，可以有空着不刷的木板。那么有 $3$ 种情况。第 $i$ 个工人不刷，或第 $j$ 块木板不刷，或枚举决策点 $k$，让第 $i$ 个工人刷第 $k+1$ 到第 $j$ 块木板。根据题意他的粉刷数不能超过 $L_i$，且必须粉刷 $S_i$，所以要满足 $k+1 \le S_i \le j$ 且 $j-k \le L_i$。综上可得转移方程：
$$ f_{i,j} = \max(f_{i-1,j},f_{i,j-1}) \\
f_{i,j} = \max_{j-L_i \le k \le S_i-1} \left\{f_{i-1,k} + P_i \times (j-k) \right\},S_i\le j$$
考虑内层循环 $j$ 和决策点 $k$ 时，可以把外层循环变量 $i$ 看作定值。那么第二个转移方程可改写为：
$$ f_{i,j} = P_i \times j + \max_{j-L_i \le k \le S_i-1} \left\{f_{i-1,k}-P_i \times k \right\},S_i \le j $$
考虑如何优化。当 $j$ 增大时，$k$ 的取值范围上界不变，下界变大，那么一定会有靠左的决策点不能再进行转移。于是我们可以维护一个决策点 $k$ 单调递增，数值 $f_{i-1,k}-P_i \times k$ 单调递减的单调队列。
而单调队列有 $4$ 个步骤。用新的决策点与队尾比较以保持队列的单调性，插入新决策点，删除队首不在约定范围内的决策点，用队首的决策点进行转移。
### [P11870](https://www.luogu.com.cn/problem/P11870) ###
数数题。
注意到将原序列加上下标后，题意转换为在小于 $n+m$ 偶数中选出 $m$ 个的方案数。答案即为 $\mathrm{C}_{\lfloor (n+m)/2 \rfloor}^{m}$。
### [P12382](https://www.luogu.com.cn/problem/P12382) ###
树形 dp。
所有点有点权，求满足两个条件下的所选点权最大值：同一层只能选一个点，父亲和儿子只能选一个。既然是一层一个点，我们可以把同一层的点记录下来，然后**按层转移**。记录当前层 dp 值的最大值和次大值，转移到下一层时，如果当前节点的父节点的 dp 值为最大值，用次大值转移，否则用最大值转移。
### [P14309](https://www.luogu.com.cn/problem/P14309) ###
树形 dp。
很好的一道题目。首先发现最后两个黑点构成的所有路径一定两两不重叠。而如果子树内黑点数为偶，就要在子树内匹配完，黑点数为奇，就会向上贡献一条边的权值。
而交换操作肯定选择颜色不同的两点，否则没有意义。将交换操作看成将黑点涂成白色，白点涂成黑色。
考虑将以上两步放在状态里，于是设 $f_{x,1/0,1/0,1/0}$ 表示以 $x$ 为根的子树，子树内是否有一个黑点变成白点，是否有一个白点变成黑点，是否多出一个黑点还没有匹配时，向上贡献的总和的最小值。
每次遍历一个子树时开一个数组 $g$ 辅助转移，枚举根的 $2\times 2\times 2 =8$ 种情况，和子树的 $8$ 种情况，有：
$$g_{i+i_1,j+j_1,k+k_1}=\min(g_{i+i_1,j+j_1,k+k_1},f_{x,i,j,k}+f_{y,i1,j1,k1}+val)$$
其中 $val$ 为 $1$ 的个数加反转的 $0$ 的个数减反转的 $1$ 的个数减多出去的 $1$ 的个数模 $2$ 的结果乘上 $x$ 到 $y$ 的边权。最后统计 $1$ 为根时的总贡献，当黑点总数为奇时，答案为 $\min(f_{1,0,0,1},f_{1,1,1,1})$；当黑点总数为偶时，答案为 $\min(f_{1,0,0,0},f_{1,1,1,0})$。
### [AT_abc207_e](https://www.luogu.com.cn/problem/AT_abc207_e) ###
dp。
设 $f_{i,j}$ 为前 $i$ 个数划分成 $j$ 段的方案数，$cnt_{i,j}$ 为前缀和模 $i$ 等于 $j$ 的合法方案数。先枚举第二维 $j$ 来确定模数，再枚举第一维。直接转移 $f_{i,j} = sum_{j,a_i\bmod j}$。
### [AT_abc318_g](https://www.luogu.com.cn/problem/AT_abc318_g) ###
圆方树。
对原图构建圆方树，如果从 $a$ 到 $c$ 的路径上存在一个方点满足其与 $b$ 直接相连，那么有解。因为方点所连的圆点在一个点双连通分量里，所以若存在满足上述条件的方点，就一定有一条路径可以经过点 $b$ 并继续前进到 $c$。实现方法是在圆方树上从 $c$ 开始 dfs，然后从 $a$ 开始递归找路径上的方点。
### [AT_abc417_d](https://www.luogu.com.cn/problem/AT_abc417_d) ###
dp，二分。
注意到值域很小，只有 $500$，而初始值很大。这说明有很多冗余操作，所以我们预处理 $b$ 的前缀和数组 $sum$，当初始值 $X$ 很大时，二分出最近的 $sum_i$ 使得 $X-sum_i \le 1000$。
然后对于 $1000$ 以内的用 $dp$ 预处理出它们的最终结果。设 $dp_{i,j}$ 表示从第 $i$ 个三元组开始，初始值为 $j$ 时的最后结果。这里 $j \le 1000$。
### [AT_abc426_f](https://www.luogu.com.cn/problem/AT_abc426_f) ###
线段树。
每次操作将区间内 $a_i$ 变为 $\max(0,a_i-k)$，询问区间操作前后差值。
考虑维护区间内最小值 $mn$，大于 $0$ 的个数 $cnt$，和减去 $k$ 的懒标记。遍历到一个子区间，如果 $cnt=0$ 跳过，否则如果完全包含于询问区间并且 $mn>k$，贡献加上 $k \times cnt$。当一个点的值小于 $0$ 时，当递归到这个点时，暴力修改这个的 $cnt =0,mn = \infty$，确保这个点不会再次被计算。其他操作与板子相同。
### [AT_dp_w](https://www.luogu.com.cn/problem/AT_dp_w) ###
线段树优化 dp。
用到了化区间为点的技巧，即只在到达区间右端点时处理贡献，可以做到不重不漏。