APIO 2019

路灯

一条长度为 n 的 n+1 个点的链。在时刻 0 时给你每条边的出现 / 不出现的状态。接下来的 q 个时刻会

1. 切换某条边的状态
2. 询问到目前为止，(a,b) 连通的时间的总和。

$n,q\le 3\times 10^5$。

摘要：区间问题转化为二维数点。

对于每个点对 (a,b)，先转化为边对。设$b'=b-1$（允许$a=b'$）。我们记录它到结束时的时间总和，设为$T(a,b')$。

那么对于时刻$i$的一次修改操作，假设修改的边是$x$，相当于$x$左右两边的点的连通性发生了变化。设与$x$连通的极大区间是$[L,R]$，那么相当于是$a\in[L,x],b\in[x,R]$的$T(a,b)$都被加上一个$q-i$（如果这条边出现）或者减掉$q-i$（如果这条边消失）。

对于一次查询操作，如果$a,b+1$当前是不连通的，那么答案就是$T(a,b)$。否则答案是$T(a,b)-(q-i)$。你要把预支的部分减掉。

上述过程实际上就是矩阵加，单点求值。把矩阵加写成 4 个前缀矩阵的形式。可以二维数点。

时间复杂度$O(n\log_2n)$。

代码

奇怪装置

给出$A,B$。定义映射$f:x\in N\to(x+\left\lfloor\frac{x}{B}\right\rfloor\bmod A,x\bmod B)$。给出$n$个区间$[l_i,r_i]$，求$|\{f(x)|x\in[l_i,r_i]\}|$（即有多少个互不相同的元素）。

$n\le 10^6,A,B,l_i,r_i\le 10^{18}$。

摘要：解同余方程。

解一个方程$f(x)=f(x+T)$，得$T=\frac{AB}{\gcd(A,B+1)}$。因此映射是有周期性的。

如果存在$l_i+T\le r_i$，那么答案就是$T$。否则可以把区间都放到$[0,T-1]$的范围，求区间并即可。

代码

桥梁

给一个 n 个点 m 条边的加权无向图，以及每条边的初始权值$(u_i,v_i,w_i)$. 有 q 个操作：

1. 把第$x$条边的边权改为$y$。
2. 问从编号为$x$的点出发，经过边权大于等于$y$的边能到达的点的个数。

$n\le 5\times 10^4,m\le 10^5,q\le 10^5,w_i\le 10^9$.

摘要：分块，离线，按权值从大到小排序，可撤消并查集，卡常。

这种数据范围的题，想不到 log 的做法，就考虑分块。将操作序列分块，每$T$个为一块。用并查集回答询问。

对于一个操作序列规模为$T$的问题，我们考虑离线处理。我们将$m$条边和操作序列分别按权值从大到小排序。按权值从大到小考虑每个操作。在操作之前我们先考虑权值大于等于当前权值的边。如果当前这条边在这$T$个操作中始终没有被修改，我们就直接把它加到并查集里。否则我们暂时忽略这条边。然后考虑当前这个操作，如果是修改操作我们也忽略，如果是询问操作，我们就想办法在$O(T)$的时间内回答询问。

回答询问：把操作序列里那些有用的（时间最晚）的修改操作找出来，如果权值比询问大就加到并查集里。然后就可以回答询问了。回答完了撤消这部分的修改即可。时间复杂度$O(T)$。注意这里并查集的复杂度是均摊$O(\log_2n)$的（吧）

这样的话，复杂度为$O(T^2+m\log_2m+T\log_2T)=O(T^2+m\log_2m)$。

总的复杂度是$O(\frac{q}{T}(T^2+m\log_2m))=O(qT+\frac{q}{T}m\log_2m)$。由于$n,m$同阶，于是当$T=\sqrt{m\log_2m}$时取得最优复杂度$O(q\sqrt{m\log_2m})$。

代码