「APIO 2019」全套题解

目录

• Problem A. 奇怪装置

• Problem B. 桥梁

• Problem C. 路灯

奇怪装置

「Luogu P5444」奇怪装置

题目描述

给定 $A, B$ 以及 $n$ 个时间区间，时钟在时刻 $t$ 会显示 $(t + \lfloor \frac{t}{B} \rfloor \bmod A, t \bmod B)$。问共会出现多少个不同的时刻。

数据范围：$n \le 10^6, 1 \le AB \le 10^{18}, 0 \le l_i \le r_i \le 10^{18}$。

思路分析

考虑两个时刻什么时候显示的二元组相等。设 $t_2 = t_1 + m B$，那么有：

$$t_1 + \lfloor \frac{t_1}{B} \rfloor \equiv t_1 + m B + \lfloor \frac{t_1 + mB}{B}\rfloor\pmod A$$

设 $\lfloor \frac{t_1}{B} \rfloor = k$，则：

$$\begin{align*} t_1 + k & \equiv t_1 + m B + k + m & \pmod A \\ 0 & \equiv m(B + 1) & \pmod A \end{align*}$$

所以 $A \vert m(B + 1)$，那么 $m$ 的最小值就是 $\frac{A}{\gcd(A, B + 1)}$，也就是说循环节的长度为 $\frac{AB}{\gcd(A, B + 1)}$。这样我们对所有时间区间处理一下然后用扫描线求它们的交即可。时间复杂度 $O(n \log n)$。

代码实现

#include <bits/stdc++.h>

桥梁

「Luogu P5443」桥梁

题目描述

给定一个带权无向图，支持修改边权，以及询问从一个点出发只经过边权不小于 $w$ 的边能到达多少个点。

数据范围：$n \le 5 \times 10^4, m, q \le 10^5$。

思路分析

如果没有修改可以离线做，有了修改后我们就考虑对操作分块，之前的修改离线加入，块内的修改暴力加入。具体地，我们将所有操作分成大小为 $b$ 的块。对于某一个块，我们离线地回答块内部的所有询问。

这时，我们可以把边分成两类：在本块内部有修改的和没有修改的。对于没有修改的边，我们将它们排序，然后离线的做；对于有修改的，它们的数量肯定不超过 $b$，我们就对于每个询问扫一遍这些边，看一下在这个询问的时间点上，它的权值是多少。这样如果 $b = \sqrt q$，那么时间复杂度是 $O(q \sqrt q \log m)$ 的。

需要注意算法的常数优化。有两个小技巧：

• 并查集在执行 $\text{fa}[u] \leftarrow v, \text{size}[v] \leftarrow \text{size}[u] + \text{size}[v]$ 后如果想要撤销，我们只需要记录 $u$，因为剩下的都可以倒推出来。
• 维护所有边按权值排序的数组时，加入每一块时不需要整体排序，只要做一次块内排序和一次归并即可。归并可以使用 std::merge() 函数，具体见代码。

另外，经试验，分块时块的大小 $b$ 为 $750$ 时常数较为优秀。

代码实现

#include <bits/stdc++.h>

路灯

在路上了。

「Luogu P5445」路灯

题目描述

有 $n + 1$ 个位置，$n$ 条道路，第 $i$ 条连接第 $i$ 个位置和第 $i + 1$ 个位置。一开始时有些边是不可用的，有 $q$ 次操作，每次更改一条边的可用性，或者查询某两个点在历史中联通过多少个时刻。

数据范围：$n, q \le 3 \times 10^5$。

思路分析

将询问看作二维平面上的点，考虑一次修改的贡献。发现两点之间连通的时刻一定是形如：$t_1$ 时刻联通，$t_2$ 时刻断开，$t_3$ 时刻联通…… 的样子，所以我们考虑差分。设总时刻数为 $T$，当前时刻为 $t$。对于一次修改，如果是将两个区间联通，我们给这两个区间对应的矩形加上 $T - t$；否则它会把某个区间断开，我们给断开后分成的两个区间对应的矩形减去 $T - t$。另外，如果询问时如果两点联通，答案要额外地减去 $T - t$。

这样，我们就把问题转化成了一个带修改的二维数点的问题，使用 CDQ 分治套树状数组 / 树套树 / K-D Tree 即可。时间复杂度 $O(n\log^2 n)$ 或 $O(n \sqrt n)$。

代码实现

#include <bits/stdc++.h>