本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-08 14:49:46

[ABC365G] AtCoder Office

题目考察：根号分治，前缀和。
题目简述：
有 $n$ 个人，$m$ 次操作，第 $i$ 次操作发生第 $t_i$ 秒，若第 $p_i$ 个人在办公室里，则他出去；否则他进去。然后有 $q$ 次询问，第 $i$ 次询问给出 $x_i,y_i$，输出有多长时间第 $x_i$ 和第 $y_i$ 个人都在办公室里。
数据范围：

• $1\le n,m,q\le 2\times 10^5$
• $\forall i\in[1,n],1\le t_i\le 10^9,1\le p_i\le n$
• $\forall i\in[2,n],t_{i-1}<t_i$
• $\displaystyle\forall i\in[1,n],2|\sum_{j=1}^m[p_j=i]$
• $1\le a_i,b_i\le n$

考虑根号分治。

对于出现次数大于等于 $B$ 的人，我们进行预处理，我们将时间节点拿出来一个一个进行处理。如果这个人在房间里，那么我们给前缀和加上前一个点到现在所过的时间。然后对于剩下的人前缀和求和即可。
对于每次询问，若两个人的进入次数都不比 $B$ 大，直接暴力两个指针统计即可。
这样时间复杂度为 $\Theta(\frac{m^2+nm}{B}+qB)$，$B$ 取 $\sqrt m$ 时时间复杂度为 $\Theta((n+m+q)\sqrt m)$。

代码