APIO2019

桥梁

将所有的操作按照时间顺序分成$T$个大小为$\frac{q}{T}$的块。对于每个块，将块内的询问按照$w_j$排序，将未被块内的操作修改过的边按照执行这个块内的操作之前的边权排序。

按照$w_j$降序枚举块内的询问，然后将所有重$w_j$的车能够通过的、“未被块内的操作修改过的”边加入；再加入块内修改过的、这次询问的时候的边权$\ge w_j$的边，查询$s_j$所在连通块的大小，然后再撤销掉加入的块内修改过的边。

复杂度是$O(\frac{q}{T}(m\log m + m\log n) + qT\log n)$，当$T$大致取到$\sqrt m$的时候最优。由于排序的那个$\log m$比并查集的$\log n$大得多，所以可以适当调大$T$。

Code

路灯

对每个时刻的序列，维护它的极长的、只包含$1$的区间构成的集合。

对每个曾经在集合中出现过的极长$1$区间，将它对每个询问的贡献分成两部分：

1. 询问的时候它还在序列中，贡献是询问的时刻 - 它被加入的时刻（由于极长$1$区间不交，所以对于一个询问，这种区间如果有则一定只有一个）；
2. 询问的时候它已经不在序列中了，贡献就是它出现过的时刻数；

而一个极长$1$区间$[l,r]$对一个询问$[a,b]$能产生贡献当且仅当$l\le a, b-1\le r$，是个二维偏序。加上“离开序列的时间小于询问的时间”就是三维偏序，可以cdq分治解决。

而第一种贡献用set维护当前时刻所有的极长$1$区间就能计算。

Code

奇怪装置

考虑什么情况下两个时刻的$(x,y)$会相同。

因为$y=(t\bmod B)$，所以这两个时刻可以写成$t,t+kB$。

$$\begin{aligned} t + \lfloor \frac{t}{B} \rfloor \equiv t + kB + \lfloor \frac{t+kB}{B} \rfloor \pmod A\\ t + \lfloor \frac{t}{B} \rfloor \equiv t + kB + \lfloor \frac{t}{B} \rfloor + k \pmod A\\ 0 \equiv k(B+1) \pmod A\\ A \mid k(B+1) \end{aligned}$$

考虑$B+1,A$的质因数分解：

$$\begin{aligned} B+1 = \prod p_i^{b_i}\\ A = \prod p_i^{a_i} \end{aligned}$$

则最小的满足条件的$k$就是

$$\begin{aligned} k_{min}\prod p_i^{\max\{a_i - b_i,0\}}\\ = \prod p_i^{a_i - \min\{b_i,a_i\}}\\ = \frac{A}{\gcd(A,B+1)} \end{aligned}$$

且其它满足条件的$k$都是它的倍数。

所以$t_1,t_2$的二元组$(x,y)$相同当且仅当$t_1\equiv t_2\pmod{k_{min}B}$

这样就转化成了简单的区间并问题。

注意考虑$k_{min}B$超过long long范围的情况。

Code