10.13

「洛谷1613」跑路

如果 $u$ 走 $2^k$ 步能到 $v$ ，那么就从 $u$ 向 $v$ 连一条边权为 $1$ 的边。

现在只需要考虑如何判断 $u$ 能否走 $2^k$ 到 $v$ ，直接倍增 floyd 即可。

「NOIP2017」逛公园

设 $dp_{u,k}$ 表示 $u\to n$ 的比最短路长至多 $k$ 的路径条数。

转移时我们需要知道走 $(u,v,w)$ 这条边后路径长度会比最短路长多少。建反图跑 dijkstra 求出每个点到 $n$ 的最短路，然后就很容易得到这个东西了。

显然存在一个可以到达的 $0​$ 环则无解。在记搜的时候如果搜到了自己就说明有可以到达的 $0​$ 环，输出 -1 即可。

「AMPPZ2014」The Captain

直接暴力连边的话边数是 $O(n^2)$ 级别的，显然过不了。

事实上将所有点按横、纵坐标分别排序后相邻的两个点连边即可。正确性显然。

这样子边数就优化到了 $O(n)$ 级别。

「NOIP2013」货车运输

把边从大到小排序后建出 Kruskal 重构树。

那么答案就相当于 Kruskal 重构树上 LCA 的权值。随便用什么办法求 LCA 即可。

注意原图可能不连通，询问时要判一下连通性，而且预处理时每个连通块都要预处理到。

「CF891C」Envy

考虑一个性质：对于一个图的所有 MST，每种边权的边的数量都相等。

因此我们把每种边权的边拿出来单独考虑。我们把并查集恢复到加该种边以前的状态，然后判断这些边加进去会不会成环即可。

现在的问题在于怎么把并查集恢复回去。显然可以可持久化并查集，但是有更优美的做法。预处理出每条边在加该种边权的边时两端点所在的连通块，这样子就很容易改回去了。

「CF241E」Flights

显然构造出来的图满足：对于一条在 $1\to n$ 的某条路径上的边 $(u,v)$，满足 $1\leq dis_v-dis_u\leq 2$。

于是只需要找到所有 $1\to n$ 路径上的边，差分约束建图，然后判负环即可。

最后输出方案时，如果该边在路径上就输出 $dis_v-dis_u$ ，否则随便输出 $1$ 或 $2$。

「POI2010」Bridges

显然可以二分答案，那么我们只需要给所有无向边定向使得定向后的有向图存在欧拉回路。

注意到有向图存在欧拉回路的充要条件是每个点的入度等于出度，也就是入度减出度等于 $0$。为了方便我们把一个点的”入度减出度“称为这个点的”度数差“。

考虑网络流。先给所有无向边随便定一个方向（假设 $u\to v$），然后从 $v$ 向 $u$ 连一条容量为 $1$ 的边，表示可以把该条边反向使得 $v$ 的度数差加 $2$，$u$ 的度数差减 $2$。

定向完后如果有一个点的度数差为奇数则一定无解，因为无论怎么反向这个点的度数差都不可能为 $0$。

继续连边。从源点向所有度数差大于 $0$ 的点连容量为 $\frac{\text{度数差}}{2}$ 的边，表示该点需要 $\frac{\text{度数差}}{2}$ 次操作；从所有度数差小于 $0$ 的点向汇点连容量为 $\frac{\text{度数差}}{2}$ 的边，意义相同。

然后跑最大流判断是否满流即可。

10.14

「AMPPZ2014」Petrol

如果每个点都是加油站，题目就相当于判断走边权 $\leq b_i$ 的边能否从 $u_i$ 到 $v_i$ 。将所有询问离线按 $b_i$ 从小到大排序，然后把边从小到大加进去，用并查集维护连通性即可。

如果去掉原图中不是加油站的点，即建一个新图，两个加油站连一条边权为最短路的边，题目就变成上面的情况了。

考虑优化这个连边。设 $nr_u$ 表示离 $u$ 最近的加油站，跑多源最短路即可求出。那么对于一条边 $(u,v,w)$ ，如果 $nr_u\neq nr_v$，则在 $nr_u$ 和 $nr_v$ 间连一条边权为 $dis_u+dis_v+w$ 的边即可。

「UVA1057」Routing

从 $2$ 走到 $1$ 相当于在反图上从 $1$ 走到 $2$。

设 $dp_{i,j}$ 表示正图上从 $1$ 走到了 $i$，反图上从 $1$ 走到了 $j$ 时最少经过点数（去重）。那么答案就是 $dp_{2,2}$。

正常的想法是每次正图上走一步或反图上走一步，跑最短路转移。

然而这样子的话，当 $i,j$ 互换时答案会多 $1$，因此还要写一个转移：$dp_{i,j}+dis_{i,j}-1\to dp_{j,i}$。

「CF1037D」Valid BFS?

我们根据在给定的 BFS 序中的位置给每个点分配一个优先级，在前面的优先级高，在后面的优先级低。

然后跑一遍 BFS，优先级高的优先入队，得到一个 BFS 序。

那么只需要判断得到的 BFS 序和题目给的 BFS 序是否相同即可。

「CF894E」Ralph and Mushrooms

显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。

缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。

考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么

$$ \frac{t(t+1)}{2}<w $$

解得

$$ t=\left\lfloor\sqrt{2x+\frac{1}{4}}-\frac{1}{2}\right\rfloor $$

那么能得到的蘑菇数是

$$ \begin{aligned} &\sum_{i=0}^t\left(w-\sum_{j=0}^ij\right)\\ =&(t+1)w-\sum_{i=0}^t\frac{i(i+1)}{2}\\ =&(t+1)w-\left(\frac{t(t+1)(2t+1)}{12}+\frac{t(t+1)}{4}\right)\\ =&(t+1)w-\frac{t(t+1)(t+2)}{6} \end{aligned} $$

「CF859E」Desk Disorder

把每个座位看作点，每个人现在的座位向想去的座位连边，那么每个点的出度至多为 $1$。

显然我们应该每个连通分量分开计算方案数，再全部乘起来。

每个连通分量内部只会有 $3$ 种情况：

• 包含自环，方案数显然为 $1$。
• 包含不是自环的环，方案数显然为 $2$。
• 是一棵树，画一画图可以发现方案数为 $sz$。

用并查集维护一下连通块的 $sz$、是否有环、是否有自环即可。

「CF852D」Exploration plan

二分答案，问题变为 $T$ 时间内能否有 $\geq k$ 个不同的点有人。

这是一个经典的模型。每个人向 $T$ 时间内能到达的点连边，这样子是一个二分图，只需要判断二分图最大匹配是否 $\geq k$ 即可。

具体的求法可以用匈牙利，也可以跑最大流。

「CF911F」Tree Destruction

显然每次选的两个点中一定有一个是直径的端点。

先求出树的直径的两个端点，以及每个点到两个端点的距离。

从一个端点开始 DFS 模拟删点，每个点会选更远的那个端点，贡献到答案中即可。

注意上面模拟删点是不能删掉直径上的点的，直径要留到最后一个个删去。

口胡起来大概就是这个样子，但是写起来细节比较多...

「CF1051F」The Shortest Statement

注意到 $m-n\leq 20$ ，所以我们随便拿一棵生成树出来，那么还会有至多 $21$ 条非树边。

那么 $u$ 到 $v$ 的最短路只有至多 $22$ 种可能：不经过任何一条非树边（或者说在树上），或者经过某一条非树边。我们只要对这些情况取个 $\min$ 即可。

树上最短路很好算，预处理到根的路径长度，用 LCA 算一下即可。

考虑后面那部分怎么算。对于每个是非树边的端点的点，求出从它出发的最短路。那么对于一条非树边 $(u,v,w)$，经过它的从 $x$ 到 $y$ 的最短路就是 $\min\left\{dis_{x,u}+w+dis_{v,y},dis_{x,v}+w+dis_{u,y}\right\}$ 。

「NOIP2018」赛道修建

我跑不过一定是因为洛谷评测机太慢了

显然二分答案，问题变为能否凑出 $m$ 条长度 $\geq mid$ 的赛道。

假设现在子节点传上来了一些赛道，长度分别为 $l_1,l_2,\cdots,l_k$。

首先对于 $l_i\geq mid$ 的赛道，直接将其作为一条赛道即可。

对于剩下的赛道，考虑将其两两匹配，即对于每个 $l_i$ 找到一个 $l_j$ 使得 $l_i+l_j\geq mid$ 且匹配数最大。

贪心地考虑，维护一个 multiset，每次 lower_bound 一个最小的 $\geq mid-l_i$ 的 $l_j$ 即可。

然后还有剩的赛道就把长度最大的向上传给父节点。

「CF1042F」Leaf Sets

假设现在在考虑 $u$ 节点，子树中传上来了 $s$ 个集合，$u$ 到第 $i$ 个集合中最深的节点的距离为 $l_i$。

将 $l_i$ 从小到大排序，找到一个最大的 $p$ 满足 $l_{p-1}+l_p\leq k$。显然把 $l_1,l_2,\cdots l_p$ 放到一个集合里，$l_{p+1},\cdots l_s$ 分别放到 $1$ 个集合里是最优的。于是把答案加上 $s-p$，再将 $l_p$ 传上去。

那么直接 DFS 做这个过程就好了。最后最上面那个集合是没有加到答案里的，所以还要加上 $1$。

另外注意要找一个度数 $\geq 2$ 的节点作为根，不然会出现一些问题。

「CF815C」Karen and Supermarket

感觉是个比较简单的题。

设 $dp_{u,i,0/1}$ 表示以 $u$ 为根的子树，选了 $i$ 个物品，物品 $u$ 用/不用消费券的最小花费。

边界为 $dp_{u,0,0}=0,dp_{u,1,0}=c_u,dp_{u,1,1}=c_u-d_u$，转移就是树上的分组背包。

答案就是最大的使得 $\min\left\{dp_{1,i,0},dp_{1,i,1}\right\}\leq b$ 的 $i$。

10.15

「CF858F」Wizard's Tour

设第 $i$ 个连通块的边数为 $w_i$，可以证明答案上界为 $\sum\left\lfloor\frac{w_i}{2}\right\rfloor$。

考虑如何达到这个上界。

先考虑一棵树的情况。维护一个 $f_u$ 表示未匹配的与 $u$ 相连的点，然后把子节点匹配即可。最后如果剩了一个就和父边匹配。这样子是可以达到上界的。

图上的情况类似，因为把一条非树边直接看作连向一个子节点的边是不会对答案有任何影响的。那么和树上相同地处理就好了。

「AGC001」Wide Swap

令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小，则应使 $a$ 的字典序尽量小。

那么题目变为：给定排列 $a_{1..n}$，如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$，求可能排列中字典序最小的。

注意到如果 $a_i,a_j$ 不可能发生交换（也就是说 $|a_i-a_j|<k$），那么两者的相对顺序不会改变。于是对于每一对不可能发生交换的 $a_i,a_j$ ，假设 $i<j$，则连一条 $i\to j$ 的有向边。那么字典序最小的拓扑序就是字典序最小的 $a$ 了，再还原回去即可得到答案。

现在的主要问题在于边数是 $O(n^2)$ 级别的，考虑优化。

考虑到如果 $i<j<k$ ，且有三条边 $i\to j,i\to k,j\to k$，那么 $i\to k$ 这条边是可以去掉的。

那么对于每个 $a_i$，只需要找到两个分别 $<a_i,>a_i$ 的 $j$，满足 $|a_i-a_j|<k$ 且尽量小，然后 $a_i$ 向 $a_j$ 连边即可。

具体的，倒序扫描所有 $a_i$，每次在线段树中求区间最小值，然后把 $a_i$ 位置修改为 $i$。

这个正确性的话可以感性理解一下...？

「CF343E」Pumping Stations

显然先把最小割树建出来。

首先有一个结论：第一问答案的上界为最小割树上所有边权之和。

下面考虑怎样达到这个上界。

考虑最小割树上的最小边，我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ，则 $a_{1..i-1}$ 中任意两点不经过该边，$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。

10.16

「ARC098F」Donation

首先有一些结论：

• 一个点只会在最后一次访问时被捐赠。
• 令 $c_i=\max\left\{a_i-b_i,0\right\}$，那么 $c_i$ 大的点会先被捐赠。

证明可以看 $\mathsf{\color{black}{h}\color{red}{yj}}$ 的题解。

于是可以考虑按 $c$ 建一棵生成树，$c_i$ 大的深度小，$c_i$ 小的深度大。具体建树过程用并查集维护一下就好了。

那么我们只需要确定某个点和子树之间的捐赠顺序。

考虑 DP。设 $dp_i$ 表示以 $i$ 为根的子树全部捐完最少需要多少钱，$sum_i$ 表示以 $i$ 为根的子树内所有 $b$ 的和。那么可以得到状态转移方程：

$$ dp_u=\min_{v\in son_u}\left\{sum_u-sum_v+\max\left\{dp_v,c_u\right\}\right\} $$

边界是当 $u$ 是叶子节点时 $dp_i=a_u+b_u$。

「SNOI2017」炸弹

最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。

然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。

统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。

「LibreOJ β Round #4」子集

一个简单的想法是每对合法的 $i,j$ 之间连一条边，那么我们相当于要求最大团。

直接求最大团肯定是求不出的。注意到最大团等于补图的最大独立集，因此我们考虑这个图的补图。

可以发现，如果 $a_i,a_j$ 奇偶性相同，那么 $i,j$ 间一定有一条边。因此在补图中，任意奇数间不会有连边，任意偶数间也不会有连边。因此补图是一个二分图。

那么只要求二分图最大独立集即可，它等于点数减二分图最大匹配。

「POI2000」病毒

显然建出 AC 自动机，那么只需要判断是否存在一个不经过任何含病毒串节点的环即可。

在建 AC 自动机时只能处理出 trie 树中就是病毒串的节点，因此要在 getfail 时顺便把这个串含不含病毒串求出来。

「POI2007」ATR

注意到 $k\leq 20$，显然可以考虑状压 DP。

设 $dp_{S,i}$ 表示已经走了 $S$ 中的城市，现在在城市 $i$ 的最短路。转移枚举去哪个城市就好了。

这题 BZOJ 上卡常，需要一些优化；原题空限 64MB ，需要一些神仙的方法压掉状态数。

另外我写这题时碰到了非常玄学的事情

「POI2007」BIU

考虑到如果两个点之间没有边，那么这两个点一定会分在一个集合里。也就是说我们要求的实际上是补图的连通块。

但是直接连边去求边数是 $n^2-m$ 级别的，显然存不下。

考虑一个很暴力的想法：每次找一个还没有找连通块的点，然后 BFS 找连通块。具体就是扩展 $u$ 时，先标记 $u$ 的所有出点，然后所有没有找到连通块的没有被标记的点都和 $u$ 在一个连通块中。

问题就是怎么维护还没有找连通块的点。这个可以维护一个链表，或者拿一个 vector 存。

10.17

「NOIP2016」蚯蚓

首先我们是没有必要每次给所有蚯蚓加 $q$ 的，只需要维护一个变量 add 表示所有蚯蚓长了多少即可。

那么一个显然的想法是用一个大根堆维护所有蚯蚓，然后直接模拟一下就好了。这样子就有 $85$ 分了。

注意到每次分出去的蚯蚓一定会成为最短的两条蚯蚓（想一想，为什么？），那么只需要开三个队列维护就好了。

「NOI2001」食物链

把每个动物拆成 $3$ 个点，分别代表它是 A、它是 B、它是 C。

如果 $u$ 和 $v$ 连通，表示如果 $u$ 满足那么 $v$ 满足，如果 $v$ 满足那么 $u$ 满足。这样子就很好判断两种动物的关系了。

那么用并查集维护一下连通性即可，每句话先判是否合法再合并。

「BZOJ4548」小奇的糖果

只考虑选的点都在线段下方的情况，在线段上方的情况可以通过将纵坐标取反一样的做。

首先考虑线段的纵坐标无限大的情况，显然线段的左右边界会卡在相邻的两个颜色相同的点之间。那么只需要将所有点按横坐标排序，维护一下上一个某种颜色的点，再用树状数组维护区间内点的个数即可。

现在把线段向下移动，假设现在纵坐标刚好比某个点 $u$ 的纵坐标小 $1$，此时线段左右边界会卡在上一个和 $u$ 颜色相同的点和下一个和 $u$ 颜色相同的点之间。我们用双端链表维护左右颜色相同的点，每次将纵坐标比线段当前纵坐标大的点删掉，然后把 $u$ 从双端链表里删掉即可。

具体实现起来有一些细节。

「CF1142B」Lynyrd Skynyrd

考虑你选了一个数之后，下一个数是唯一确定的，而且肯定越靠前越好。

设 $nxt_i$ 表示选了 $a_i$ 之后下一个数选哪个。特别的，如果不存在能选的下一个数，$nxt_i=\infty$。那么我们就相当于要询问 $[l,r]$ 中是否存在一个 $i$ 满足跳 $n-1$ 次 $nxt$ 后跳到的数还在 $[l,r]$ 中。

倍增预处理出一个 $x_i$ 表示每个数跳 $n-1$ 次 $nxt$ 跳到的位置，那么我们只需要知道 $[l,r]$ 内 $x_i$ 的最小值是否在 $[l,r]$ 内即可。这个直接用 ST 表维护就好了。

实际实现的时候为了避免 $\infty$ 的边界问题可以反过来，即设 $nxt_i$ 表示选了 $a_i$ 之后上一个数是哪个（不存在时设为 $0$），然后最小值改成最大值即可。

「NOI2016」区间

考虑把所有区间按长度从小到大排序，然后枚举最小的区间 $i$，往右扩展到一个 $[i,j]$ 内所有区间包含某个点 $m$ 次的区间 $j$。

这样子的话，显然可以从 $[i,j]$ 中选出 $m$ 个满足条件的区间，于是只要拿 $len_j-len_i$ 更新答案即可。

进一步发现，当 $i$ 增大时 $j$ 是不降的，因此每次可以直接拿上次的 $j$ 来继续扩展。

至于如何判断是否包含某个点 $m$ 次，离散化后拿线段树维护一下区间 $\max$ 值即可。

「SDOI2009」虔诚的墓主人

设一块墓地上、下、左、右的常青树数量分别为 $u,d,l,r$，那么这块墓地的虔诚值显然为

$$ {u\choose k}{d\choose k}{l\choose k}{r\choose k} $$

直接考虑每块墓地显然是不行的，我们考虑横坐标相同、纵坐标连续的一段墓地。

这段墓地的虔诚值总和为

$$ {u\choose k}{d\choose k}\sum_{i=y_1}^{y_2}{l_i\choose k}{r_i\choose k} $$

考虑如何维护 $\sum$ 后面的东西，显然可以用一棵支持区间求和的线段树来维护，每次扫过一个点后就修改掉即可。

另外模数是 $2^{31}$ ，可以使用 int 的溢出。

代码写起来感觉有点复杂...

「CTSC2018」混合果汁

显然答案是可以二分的，那么只需要判断用美味度 $\geq d$ 的果汁能不能在不超过 $g$ 元的情况下凑出 $L$ 升即可。

考虑我们一定优先买便宜的果汁，因此可以维护一棵以价格为下标的权值线段树，那么在线段树上二分即可判断是否可行。

现在还有一个美味度 $\geq d$ 的限制，于是只要按 $d$ 从大到小插入一棵主席树就好了。

「国家集训队」middle

二分答案，将 $\geq mid$ 的数视作 $1$，$<mid$ 的数视作 $-1$，那么如果 $[a,b]$ 的后缀最大值加 $[c,d]$ 的前缀最大值加 $[b+1,c-1]$ 的和 $> 0$，说明 $mid$ 可以更大。

前后缀最大值和区间和用线段树维护即可。但是由于空间问题，我们不能对每个 $mid$ 都开一棵线段树。

把 $a_i$ 从小到大排序，注意到相邻两个 $a_i$ 的线段树只差了一个位置（一个 $1$ 变成了 $-1$），因此用主席树替代线段树即可。

「CF765F」Souvenirs

首先将所有询问离线并按右端点排序。

假设现在右端点扫到了 $i$，考虑维护一个 $ans_j$ 表示 $[j,i]$ 的答案。

考虑用线段树维护这个 $ans$。只需要线段树上每个节点维护对应的区间内所有数，每次加一个数进来就二分一下取个 $\min$ 更新 $ans$ 即可。

这样子复杂度看起来非常的高。考虑到 $ans$ 是不降的，因此如果右边的某个区间在修改后的答案比左边的一个区间还小的话，那么左边那个区间可以不修改，对答案不会有任何影响。然后就可以过了...？

「PA2014」Kuglarz

设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。

考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。

因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ 间连一条边权为 $c_{i,j}$ 的无向边。那么最小生成树就是答案。

「洛谷3979」遥远的国度

这种带换根的树上操作题就是 LCT板子 分类讨论...

首先那个链修改是不受换根影响的，我们只需要讨论子树查询。

设以 $1$ 为根时 $u$ 子树的点的 dfs 序在 $[st_u,ed_u]$ 内。假设查询的是 $u$ 子树，根是 $rt$，那么大概有以下几种情况：

• $u=rt$，直接查所有点的最小值即可。
• $\operatorname{lca}(u,rt)\neq u$，此时 $u$ 的子树就是以 $1$ 为根时 $u$ 的子树，直接查询 $[st_u,ed_u]$ 即可。
• $\operatorname{lca}(u,rt)=u$，此时我们找到一个以 $1$ 为根是 $u$ 的子节点 $v$，满足 $rt$ 在子树 $v$ 内，那么此时 $u$ 的子树就是所有点去掉以 $1$ 为根时 $v$ 的子树。于是查询 $[1,st_v-1]\bigcup[ed_v+1,n]$ 即可。

写起来也比较休闲，只要码一堆板子上去就好了。

10.18

「CF650E」Clockwork Bomb

设 $fa_1[u]$ 表示 $u$ 在第一棵树上的父亲，$fa_2[u]$ 表示 $u$ 在第二棵树上的父亲。

现在在第一棵树上 DFS。假设现在在 $u$，如果 $(fa_1[u],u)$ 没有在第二棵树上出现过，那么就把它换成 $(fa_2[u],u)$。

这样子会有一个问题，就是可能 $(fa_2[u],u)$ 已经被连上了。这种情况只要往上跳 $fa_2$ 直到没有连边即可。这个过程并查集优化一下就好了。

容易发现这样子可以达成目标，而且次数达到了下界。

「CF1004E」Sonya and Ice Cream

显然选的路径是直径的一部分。为了方便，把直径上的点重编号为 $1\sim cnt$。

我们把这棵树想象成一条链上挂了一些子树。那么设一个 $maxdis_i$ 表示 $i$ 子树中到 $i$ 最远的点的距离。

一个暴力做法是枚举选的路径 $[l,r]$，此时最大距离就是 $1\sim l$ 的距离、$r\sim cnt$ 的距离、$\max_{i=l}^r\left\{maxdis_i\right\}$ 三者的最大值。这样子大概是 $O(n^3)$ 的。

考虑到我们选的路径一定越长越好，因此只需要枚举左端点 $l$，右端点即为 $l+k-1$。这样子就变成 $O(n^2)$ 了。

剩下的就很简单了。我们用 ST 表求 $maxdis$ 的最大值，这样就是 $O(n\log n)$ 的了。

「POI2015」KIN

首先这个东西长得和最大子段和很类似，于是我们先把 GSS3 的代码蒯过来。

考虑怎么让它变成最大子段和。为了方便，设 $pre_i​$ 表示上一个和 $i​$ 电影相同的。

我们从左往右扫，假设现在扫到了 $i​$，那么在线段树中把 $i​$ 位置赋值为 $w_{f_i}​$，把 $pre_i​$ 位置赋值为 $-w_{f_i}​$，把 $pre_{pre_i}​$ 位置赋值为 $0​$。

这样为什么是对的呢？最大子段如果只包含了 $i​$，那么没有什么影响；如果同时包含了 $pre_i​$ 和 $i​$，那么贡献抵消掉了，也没有影响；如果只包含了 $pre_i​$，那么这个之前就算过了，所以还是没有什么影响。

然后 $pre_{pre_i}​$ 赋值为 $0​$ 是因为后面两个已经抵消了，所以 $pre_{pre_i}​$ 要赋值为 $0​$ 避免多减一些东西。

10.20

「CF600E」Lomsat gelral

树上启发式合并板子题啊...

维护一个 $cnt_i$ 表示第 $i$ 种颜色的出现次数，$num_i$ 表示有多少种颜色出现 $i$ 次，$sum_i$ 表示所有出现 $i$ 次的颜色的编号和。这样子计算贡献显然是 $O(1)$ 的。

那么在树上 DFS，重复以下过程：

• 递归处理所有轻儿子，并消去贡献。
• 递归处理重儿子，并保留贡献。
• 将轻儿子的信息合并到重儿子保留的贡献中。
• 若当前节点不是父节点的重儿子，消去贡献。

复杂度 $O(n\log n)$，但是我不会证。

「CF741D」Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths

其实我没写这题

考虑到字符不超过 $22$ 种，因此可以状压。问题变为每棵子树中是否存在一条异或和有至多一个 $1$ 的路径。

维护一个 $f_i$ 表示到根的路径异或和为 $i$ 的点的最大深度，dsu on tree 即可。

然后这个更新答案和合并信息的过程挺像点分治的，一条路径和两条路径的情况都算一下就好了。

「SDOI2015」寻宝游戏

通过手玩一些数据可以发现，我们一定会从一个有宝藏的点出发，而且按照 DFS 序遍历所有有宝藏的点会最优。

不妨设现有的有宝藏的点按 DFS 序排序后为 $a_1,a_2,a_3,\cdots,a_k$，那么我们要求的就是 $\operatorname{dis}(a_1,a_2)+\operatorname{dis}(a_2,a_3)+\cdots\operatorname{dis}(a_k,a_1)$。

考虑加入一个点 $u$ 后答案的变化量。设 $a$ 中 $u$ 的DFS 序的前驱为 $L$，后继为 $R$，那么变化量为 $\operatorname{dis}(L,u)+\operatorname{dis}(u,R)-\operatorname{dis}(L,R)$。删除类似。

于是用 std::set 维护所有有宝藏的点就好了。

感觉这就是虚树的思想...？

10.21

「LOJ121」「离线可过」动态图连通性

线段树分治。感觉还是挺简单的？

考虑每条边出现的时间都是若干段区间。我们以时间为下标建一棵线段树，然后在每条边出现的区间挂上这条边。然后我们把询问挂在叶节点上。

DFS 这棵线段树，每次到一个节点后就把这个节点上挂的所有边连上。这样子到叶节点时该时间点所有的边都已经连上了，直接询问是否连通即可。

这个过程中用一个可撤销并查集维护连通性即可。

「BZOJ5216」公路建设

以边的编号为下标建一棵线段树，每个节点开一个 vector 存一下对应区间内哪些边在最小生成森林内。

这样子合并两个节点就是先 std::merge 得到排好序的边集，然后 Kruskal 求最小生成森林。

查询就把每个区间合并起来就好了。

感觉这个题实现不好的话容易写得很长...

「NOI2009」二叉查找树

首先应该可以一眼看出来这就是个 treap，然后改权值就相当于旋转。

考虑到 treap 旋转后中序遍历是不变的，因此我们可以先给所有节点按数据值排个序，这样就能得到中序遍历了。

进一步发现，中序遍历中一段区间在 treap 上是连通的一部分。因此可以考虑区间 DP。

设 $dp_{i,j,k}​$ 表示 $[i,j]​$ 内的节点，根节点权值 $\geq k​$ 的最小代价。因为 $k​$ 一维很大，所以我们提前将权值离散化。

转移时枚举一个根节点 $l​$，然后有两种转移：

• 更改根节点的权值：$dp_{i,l-1,k}+dp_{l+1,j,k}+K+sum(i,j)\to dp_{i,j,k}​$。
• 不更改根节点的权值：$dp_{i,l-1,w_l}+dp_{l+1,r,w_l}+sum(i,j)\to dp_{i,j,k}​$。

这里的 $sum(i,j)​$ 表示 $[i,j]​$ 内节点的访问频度之和，$w_l​$ 表示 $l​$ 的权值。

使用记搜转移即可。答案为 $dp_{1,n,1}​$。

「CF55D」Beautiful numbers

显然是数位 DP，但是要想清楚这个条件怎么处理。

注意到如果 $a_1|d,a_2|d,\cdots,a_k|d​$，那么 $\operatorname{lcm}(a_1,a_2,\cdots,a_l)|d​$。因此我们只需要知道这个数对每一位上的数的 $\operatorname{lcm}​$ 取模的结果。

但是 $\operatorname{lcm}​$ 是动态变化的，所以不好直接对 $\operatorname{lcm}​$ 取模的结果。因此我们记对 $\operatorname{lcm}(1,2,\cdots,9)=2520​$ 取模的结果。

到这里可以设出状态了。根据套路设 $dp_{i,j,k,lim}​$ 表示前 $i​$ 位对 $2520​$ 取模的结果是 $j​$，前 $i​$ 位上的数的 $\operatorname{lcm}​$ 是 $k​$，是否顶着上界的方案数。转移什么的就很简单了。

现在有一个问题是这个 DP 数组是开不下的。注意到 $\operatorname{lcm}​$ 一定是 $2520​$ 的因数，因此第三维的大小实际上只有 $\mathbf{d}(2520)=48​$ 。这样子就开得下了。

还有一个问题，就是这样子可能会 TLE on test #11。考虑到所有没有顶着上界的状态的方案数都是一样的，因此我们可以把 $lim​$ 一维去掉（即只记忆化没有顶着上界的），然后就只需要在一开始 memset 一次了。这样子就可以过了。

「HAOI2008」硬币购物

考虑容斥。设 $f(S)$ 为 $S$ 中硬币一定超过限制，不在 $S$ 中硬币任意，买 $s$ 价值的方案数。

那么答案为

$$ \sum_{S}(-1)^{|S|}f(S) $$

考虑计算 $f(S)$。显然 $S$ 中的硬币至少用了 $d_i+1$ 个，也就是说至少会有 $\sum c_i(d_i+1)$ 价值的物品。此时剩下的 $s-\sum c_i(d_i+1)$ 价值是随便凑的，因此做一个完全背包即可。

「HNOI2012」集合选数

我们考虑构造一个矩形 $a​$ 满足

$$ a_{i,j}=\begin{cases}1,&i=1,j=1\\2a_{i-1,j},&i>1\\3a_{i,j-1},&j>1\end{cases} $$

这样子问题就变为在这个矩形中选若干个数，相邻的不能选，求方案数。

我们需要保证 $a_{i,j}\leq n​$，因此行数不会超过 $17​$，列数不会超过 $11​$，因此可以状压 DP。设 $dp_{i,S}​$ 表示前 $i​$ 行，第 $i​$ 行选了 $S​$ 的方案数，枚举上一行状态转移即可。

但是这样会有一个问题，就是有一些数（例如 $5​$）没有出现在矩形中。因此我们对于每个没有出现过的数，以其为 $a_{1,1}​$ 构造出这样一个矩阵跑状压 DP，再将方案数乘起来即可。

「NOIP2016」换教室

先跑 floyd 求出任意两个教室之间的最短路。注意处理一下自环和重边。

考虑 DP。设 $dp_{i,j,0/1}​$ 表示前 $i​$ 个教室，交了 $j​$ 份申请，第 $i​$ 个教室是否交了申请的最小期望体力。

先考虑 $dp_{i,j,0}$ 的转移。我们考虑上一个教室交没交申请，可以得到

$$ dp_{i,j,0}=\min\begin{cases}dp_{i-1,j,0}+dis_{c_{i-1},c_i}\\dp_{i-1,j,1}+(1-k_{i-1})dis_{c_{i-1},c_i}+k_{i-1}dis_{d_{i-1,c_i}}\end{cases} $$

$dp_{i,j,1}$ 的转移类似。其实是太长了 M_sea 懒得写了

然后答案就是 $\min_{i=0}^m\left\{dp_{n,i,0},dp_{n,i,1}\right\}$ 。

「HNOI2018」道路

首先你要把题目看懂。

设 $dp_{u,i,j}​$ 表示节点 $u​$ 向上有 $i​$ 条未翻修的公路、$j​$ 条未翻修的铁路的最小不便利值。

转移时，考虑该节点修公路还是修铁路：

$$ dp_{u,i,j}=\min\begin{cases}dp_{s_u,i,j}+dp_{t_u,i,j+1}\\dp_{s_u,i+1,j}+dp_{t_u,i,j}\end{cases} $$

边界是当 $u​$ 是乡村时，$dp_{u,i,j}=c_u(a_u+i)(b_u+j)​$。

然而这样子写得不好可能会 MLE，需要注意一下...

「NOIP2014」飞扬的小鸟

设 $dp_{i,j}​$ 表示飞到 $(i,j)​$ 的最少点击次数。

这样子往上飞就是完全背包，往下飞就是 01 背包。注意判一下超出 $m​$ 的情况。

写起来细节感觉非常的多...反正我写了 2/3 节晚自习

「APIO2014」连珠线

这题又写了我 2/3 节晚自习

首先考虑连线的过程。可以发现，以最先加的点为根，所有的蓝线都会是儿子-自己-父亲的形式。

于是我们枚举根，然后 f。设 $f_{u,0/1}$ 表示以 $u$ 为根的子树，$u$ 是或不是蓝线中点的最大得分。

首先考虑 $f_{u,0}$ 的转移。此时每个子节点要么不是中点，要么是中点。于是有

$$ f_{u,0}=\sum_{v\in son_u}\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\} $$

再考虑 $f_{u,1}$ 的转移。此时我们钦定一个子节点作为与 $u$ 蓝线相连的点。于是有

$$ f_{u,1}=f_{u,0}+\max_{v\in son_u}\left\{-\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\}+f_{v,0}+w_{u,v}\right\} $$

这样子是 $O(n^2)$ 的，结合随机算法可能可以拿 57 分。

因为我们要求每个节点作为根时的 $f​$ 值，因此可以考虑换根 DP。

我们考虑 $u$ 的一个子节点 $v$ 变为根时，$f_{u,0/1}$ 都应将 $v$ 的贡献去掉。$f_{u,0}$ 可以直接减去 $v$ 的贡献，而 $f_{u,1}$ 需要维护一个次大值来去除 $v$ 的贡献。

然后去除贡献之后直接把 $u$ 的 $f$ 值算到 $v$ 里去，就可以得到以 $v$ 为根时的 f 值了。

具体的，在代码实现中维护一个 $dp_{u,0/1,v}​$ 表示去掉子节点 $v​$ 后 $f_{u,0/1}​$ 的值，同时维护一下去掉子节点 $v​$ 后子树中 $-\max\left\{f_{v,0},f_{v,1}+w_{u,v}\right\}+f_{v,0}+w_{u,v}​$ 的最大值。然后换根时把 $f_{u,0/1}​$ 设为 $dp_{u,0/1,v}​$ ，然后把 $u​$ 的贡献加到 $v​$ 中去，再更新一下答案并递归处理即可。

感觉不是很讲得清啊...不过应该看看代码就能看懂了。

10.22

「JOI 2019 Final」勇者比太郎

看懂题后可以发现，我们要求每个 J 右边的 O 的数量乘下面的 I 的数量之和。

预处理前缀和后枚举每个 J 计算即可。时间复杂度 $O(n^2)$。

「CF5E」Bindian Signalizing

首先我们要破环为链。这里有一个技巧是选最高的位置 $maxpos​$ 拆开，因为不会有一对点跨过最高点。

然后处理出以下 $3​$ 个东西：

• $L_i​$：$i​$ 左边第一个比它高的位置。
• $R_i​$：$i​$ 右边第一个比它高的位置。
• $cnt_i​$：$(i,R_i)​$ 内和 $i​$ 一样高的数的个数。

这 $3​$ 个东西可以单调栈预处理出来。

然后答案差不多是

$$ \sum_{i\neq maxpos}cnt_i+[L_i\neq maxpos]+[R_i\neq maxpos] $$

容易发现这样子是不重不漏的。

但是这里没有把最高的那个算进去，所以我们还要把最高的那个的贡献算一遍。

代码细节比较多，各种情况要考虑清楚...

「JOI 2019 Final」有趣的家庭菜园 3

设 $dp_{i,j,k,0/1/2}$ 表示前 $i$ 位，有 $j$ 个 G、$k$ 个 Y，第 $i$ 位的颜色是 R/G/Y 的最小代价。

转移很显然枚举新加的一位的颜色，那么我们只需要求出一个 $cost(x,y,z,0/1/2)$ 表示前 $x+y+z$ 位有 $x$ 个 R、$y$ 个G、$k$ 个 Y ，第 $x+y+z+1$ 位的颜色是 R/G/Y 的最小代价。

这个东西比较好求：首先我们补一个 $x+y+z+1$ 位的颜色，然后其它两种颜色如果有不够的也要补。代码大概长这样：

// pos[i][j] 表示第 j 个颜色 i 的下标
// sum[i][j] 表示前 j 位有多少个颜色 i
inline int cost(int x,int y,int z,int k) {
    int p=x+y+z+1;
    if (x>cnt[0]||y>cnt[1]||z>cnt[2]) return inf;
    if (k==0) {
        if (x+1>cnt[0]) return inf;
        int q=pos[0][x+1];
        return q-p+max(0,y-sum[1][q])+max(0,z-sum[2][q]);
    }
    if (k==1) {
        if (y+1>cnt[1]) return inf;
        int q=pos[1][y+1];
        return q-p+max(0,x-sum[0][q])+max(0,z-sum[2][q]);
    }
    if (k==2) {
        if (z+1>cnt[2]) return inf;
        int q=pos[2][z+1];
        return q-p+max(0,x-sum[0][q])+max(0,y-sum[1][q]);
    }
}

然后就可以 $O(1)​$ 转移了，所以时间复杂度 $O(n^3)​$。

「AGC009C」Division into Two

为了方便，令 $A>B$。

那么显然，如果存在 $3$ 个数满足两两之差小于 $B$，无解。所以把这个先判掉。

设 $dp_i$ 表示第一个集合最后选的数是 $i$ 的方案数，转移枚举上一个数是谁即可。

考虑如果 $j$ 能转移到 $i$，那么 $j$ 会具有哪些性质。可以发现：

• $j<i$
• $S_i-S_j\geq A$
• 对于 $[j+1,i-1]$ 中任意两个数 $x<y$，满足 $S_y-S_x\geq B$

可以发现 $j​$ 的取值范围是一个区间，于是前缀和优化一下就好了。时间复杂度 $O(n)​$。

「HNOI2008」玩具装箱TOY

设 $dp_i​$ 表示前 $i​$ 个玩具的最小费用，$sum_i​$ 表示 $\sum_{j=1}^ic_j​$，容易得到状态转移方程

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+(i-j-1+sum_i-sum_j-L)^2\right\} $$

为了方便，我们令 $L$ 加 $1$。

于是

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+(i-j+sum_i-sum_j-L)^2\right\} $$

我们把 $\min$ 中的东西大力拆开，并把所有项分为三类：

• 与 $j​$ 无关的：$i^2+2isum_i-2iL+sum_i\!^2+L^2-2sum_iL​$。
• 只和 $j$ 有关的：$dp_j+j^2+2jsum_j+2jL+sum_j\!^2+2sum_jL$。
• 既和 $i​$ 有关又和 $j​$ 有关的：$-2(i+sum_i)(j+sum_j)​$。（这个是因式分解之后的式子）

令 $y_i=dp_i+i^2+2isum_i+2iL+sum_i\!^2+2sum_iL$，$x_i=(i+sum_i)$，$k_i=2(i+sum_i)$，$pre_i=i^2+2isum_i-2iL+sum_i\!^2+L^2-2sum_iL$，那么状态转移方程改写为

$$ dp_i=pre_i+\min_{j=0}^{i-1}\left\{-k_ix_j+y_j\right\} $$

把每个转移点看做一个点 $(x_j,y_j)$，那么我们相当于要找一个点，使得斜率为 $k_i$ 的经过它的直线的纵截距最小。

可以发现可能满足条件的点一定在下凸壳上，因此我们只需要想办法维护下凸壳就好了。

注意到 $k_i​$ 和 $x_j​$ 都是单增的，因此用单调队列来维护下凸壳，每次队头即为最优转移点。

「APIO2010」特别行动队

推完式子一遍码对了很舒服。

设 $dp_i$ 表示前 $i$ 个士兵的最大战力，$sum_i$ 表示 $\sum_{j=1}^ix_i$，容易得到状态转移方程

$$ dp_i=\max_{j=0}^{i-1}\left\{dp_j+a(sum_i-sum_j)^2+b(sum_i-sum_j)+c\right\} $$

把 $\max$ 中的东西大力拆开，并把所有项分为三类：

• 与 $j​$ 无关的：$asum_i\!^2+bsum_i+c​$
• 只和 $j​$ 有关的：$dp_j+asum_j\!^2-bsum_j​$
• 既和 $i​$ 有关又和 $j​$ 有关的：$-2asum_isum_j​$

令 $pre_i=asum_i\!^2+bsum_i+c​$，$y_i=dp_i+asum_i\!^2-bsum_i​$，$k_i=2asum_i​$，$x_i=sum_i​$，那么状态转移方程改写为

$$ dp_i=pre_i+\max_{j=0}^{i-1}\left\{-k_ix_j+y_j\right\} $$

因为要求的是最大值，而且 $x_i​$ 单增、$k_i​$ 单减，所以可以用单调队列维护上凸壳，队头为最优决策。

10.23

「JSOI2011」柠檬

首先有一个显然的性质：每一段左右端的贝壳大小一定相同，而且这一段的 $s_0​$ 一定是左右端贝壳的大小。因为如果不是这样的话，我们显然可以把端点单独成一段，然后答案会变大。

设 $dp_i​$ 表示前 $i​$ 个贝壳最多可以得到多少柠檬，$c_i​$ 表示 $i​$ 是第几个 $a_i​$ 大小的柠檬，容易得到状态转移方程

$$ dp_i=\max_{j=1}^i\left\{dp_{j-1}+a_i(c_i-c_j+1)^2\right\} $$

把 $\max$ 里的东西拆开，并把所有项分为三类：

• 与 $j$ 无关的：$a_ic_i\!^2+2a_ic_i+a_i$
• 只和 $j$ 有关的：$dp_{j-1}+a_ic_j\!^2-2a_ic_j$（注意， $a_i=a_j$）
• 既和 $i$ 有关又和 $j$ 有关的：$-2a_ic_ic_j$

令 $pre_i=a_ic_i\!^2+2a_ic_i+a_i$，$k_i=2c_i$，$x_i=a_ic_i$，$y_i=dp_{i-1}+a_ic_i\!^2-2a_ic_i$，那么状态转移方程改写为：

$$ dp_i=pre_i+\max_{j=1}^{i}\left\{-k_ix_j+y_j\right\} $$

因为要求的是最大值，所以维护上凸壳；因为 $x_i$ 单增、$k_i$ 单增，所以用单调栈维护上凸壳，栈顶为最优决策。

注意每次要把自己先加到单调栈中去再取栈顶转移。

「ZJOI2010」基站选址

设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。

这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。

考虑转移。枚举上一个建站的位置可以得到

$$ dp_{i,j}=\min_{p}\left\{dp_{i-1,p}+cost(p,j)\right\} $$

这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会产生多少的补偿费。

考虑优化。先二分出每个村庄最左、最右的能够覆盖到它的村庄 $L_i$ 和 $R_i$。那么如果 $[L_i,R_i]$ 内没有基站，就会产生 $w_i$ 的补偿费。

也就是说，对于每个 $R<j​$ 的村庄 $p​$，它会给所有的 $cost(i,j)\,(i<L_p)​$ 加上 $w_p​$。

那么我们就可以线段树优化 DP 了，每次转移就查一下区间最小值，然后对于每个 $R_p=j​$ 的村庄 $p​$ 做一次 $1\sim L_i-1​$ 的区间加即可。

「CF960F」Pathwalks

一个显然的 DP 是设 $dp_i$ 表示前 $i$ 条边的答案，容易写出转移

$$ dp_i=\max_{j<i,v_j=u_i,w_j<w_i}\left\{dp_j\right\}+1 $$

我们需要想办法优化找 $\max$ 的过程。

一个简单的想法是对每个点维护一棵权值线段树，这样子每次只需要查询一下第 $u_i$ 棵线段树中 $[0,w_i-1]$ 的最大值，然后将第 $v_i$ 棵线段树中 $w_i$ 位置修改为 $dp_i$。

然而这样子开不下。但是注意到有用的点比较少，因此动态开点即可。

「AMPPZ2014」The Prices

为什么泥萌都写 $\mathcal{O}(nm2^m)​$ 啊 QAQ

首先 $\mathcal{O}(n4^n)$ 的暴力 DP 应该很容易想 然而和正解没有什么关系

设 $f_S$ 表示只在一个商店购买 $S$ 中物品的最小花费。这个很容易预处理出来。

设 $dp_S​$ 表示购买 $S​$ 中物品的最小花费，容易写出转移

$$ dp_S=\min_{T\subseteq S}\left\{f_T+dp_{S-T}\right\} $$

这个可以理解成一个背包。

时间复杂度 $\mathcal{O}(n2^m+3^m)$。

「POI2011」Lightning Conductor

$$ \begin{aligned} &a_j\leq a_i+p_i-\sqrt{|i-j|}\\ \Longrightarrow&p_i\geq a_j+\sqrt{|i-j|}-a_i \end{aligned} $$

也就是说，我们要对每个 $i$ 找到一个最大的 $a_j+\sqrt{|i-j|}$。因为有绝对值不好处理，所以我们正反跑两遍。我们只考虑正着的情况，即求

$$ \max_{j=1}^{i}\left\{a_j+\sqrt{i-j}\right\} $$

设 $f_j(i)=a_j+\sqrt{i-j}$，可以发现在 $i$ 增大的过程中如果 $f_p$ 超过了 $f_q$，那么 $f_p$ 就永远比 $f_q$ 大了。也就是说，这个东西满足决策单调性。

因此我们可以开一个单调队列，维护一下相邻两个元素的临界点 $k$（一个超过另一个的位置）。显然我们需要保证 $k$ 单增，因为如果 $k_{i,i+1}\geq k_{i+1,i+2}$，那么显然 $f_{i+1}$ 是没用的。

那么每次把自己加到单调队列中后，再把队头所有 $k_{h,h+1}\leq i$ 的去掉（这些不可能称为最优决策点），然后队头就是最大值了。

至于这个临界点怎么求？直接二分就好了啊。

「NOI2009」诗人小G

设 $dp_i​$ 表示前 $i​$ 句诗的最小不协调度，$sum_i=i+\sum_{j=1}^ilen_i​$，容易写出状态转移方程

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+|sum_i-sum_j-1-L|^P\right\} $$

我们令 $f_i(x)=dp_i+|sum_x-sum_i-1-L|^P$，可以发现 $f_i(x)$ 是关于 $sum_i-1-L$ 对称的，而且每个 $f_i(x)$ 的形状都一样。再进一步，这个 DP 是具有决策单调性的。

那么只需要用单调队列维护一下就好了，具体做法和上一题是一样的...

然后这题有一些要注意的地方：

• 答案会爆 long long，请开 long double。
• 自带的 pow 非常慢还掉精度，请手写一个快速幂。

「POI2007」ZAP

$$ \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\ =&\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[\gcd(i,j)=1]\\ =&\sum_{i=1}^{n/d}\mu(i)\Big\lfloor\frac{n}{id}\Big\rfloor\Big\lfloor\frac{m}{id}\Big\rfloor \end{aligned} $$

线性筛 $\mu​$ 后数论分块计算即可。