[ABC365G] AtCoder Office 题解

zrl123456 · 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)。

代码