G - AtCoder Office

Problem Statement

$N$ people work at the AtCoder office.

The office keeps records of entries and exits, and there have been $M$ entries and exits since the records began.

The $i$-th $(1\leq i\leq M)$ record is represented by a pair of integers $(T_i, P_i)$, indicating that at time $T_i$, the $P_i$-th person either entered the office if they were outside, or exited the office if they were inside.

It is known that all people were outside the office at the beginning of the records, and they are outside now.

Answer $Q$ queries in the following format.

For the $i$-th $(1\leq i\leq Q)$ query, you are given a pair of integers $(A_i, B_i)$. Find the total length of the periods during which both the $A_i$-th and $B_i$-th persons were inside the office since the records began.

Constraints

• $2\leq N\leq2\times10^5$
• $2\leq M\leq2\times10^5$
• $1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9$
• $1\leq P_i\leq N\ (1\leq i\leq M)$
• For every $1\leq p\leq N$, the number of indices $i$ such that $P_i=p$ is even.
• $1\leq Q\leq2\times10^5$
• $1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)$
• All inputs are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$
$Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

Output

Print $Q$ lines. The $i$-th line $(1\leq i\leq Q)$ should contain the answer to the $i$-th query.

Sample Input 1

3 8
10 1
20 2
30 1
40 3
60 3
70 1
80 2
90 1
3
1 2
1 3
2 3

Sample Output 1

20
0
20

The following diagram shows the time each of the three people spent inside the office.

The answers to each query are as follows:

• The 1st and 2nd persons were both inside the office from time $20$ to time $30$ and from time $70$ to time $80$. The lengths of these two periods are both $10$, so print the total, which is $20$.
• The 1st and 3rd persons were never inside the office at the same time, so print $0$.
• The 2nd and 3rd persons were both inside the office from time $40$ to time $60$. The length of this period is $20$, so print $20$.

Sample Input 2

10 20
10257 9
10490 4
19335 1
25893 5
32538 9
33433 3
38522 9
40629 9
42896 5
52106 1
53024 3
55610 5
56721 9
58286 9
63128 3
70513 3
70977 4
74936 5
79883 9
95116 9
7
1 3
3 9
1 9
4 9
1 5
5 9
3 5

Sample Output 2

18673
2107
15310
25720
17003
10317
16848

解题思路

  题意大概是每个人有若干个互不相交的区间，每次询问两人交集的长度是多少。看到时限 $5$ 秒一般时间复杂度都是带根号的，因此容易想到分块或根号分治的做法。

  由于所有人的区间总数是恒定的，因此可以考虑根据每个人的区间数量进行分类。设阈值 $M = O(\sqrt{m})$，那么区间数量超过 $M$ 的人数大概就是 $O(\frac{m}{M}) = O(\sqrt{m})$ 级别。对于每个区间数量超过 $M$ 的人，我们可以通过遍历 $m$ 条记录预处理出该人与其他人的交集长度，时间复杂度为 $O((n+m) \sqrt{m})$。因此在询问时，如果两人的区间数量都不超过 $M$，直接暴力枚举区间求交集即可，时间复杂度为 $O(\sqrt{m})$，否则直接查表。

  思想比较简单，但实现就相对困难。下面先给出如何通过 $O(m)$ 的方法求出第 $i$ 个人与其他人的交集。由于 $m$ 条记录对应的时间没用重复且依次递增，这相当于进行了离散化。定义 $\mathrm{last}_j$ 表示第 $j$ 个人上一条记录的编号，如果上条记录对应区间右端点则设为 $0$。定义前缀和 $s_j$ 表示第 $i$ 个人的前 $j$ 条记录中区间的总长度，转移方程为 $\displaylines{\begin{cases} s_j = s_{j-1} + t_j - t_{j-1}, &\mathrm{last}_i \ne 0 \\ s_j = s_{j-1}, &\mathrm{last}_i = 0 \end{cases}}$。因此当遍历到第 $j$ 条记录时，如果对应的是第 $p_j$ 个人的右端点，那么第 $i$ 个人与第 $p_j$ 个的人的交集长度就是 $s_{j} - s_{\mathrm{last}_{p_j}}$，将该结果累加到两人的总交集长度中。

  剩下的就是如何求出两个区间数量不超过 $M$ 的人的交集长度。每个人的区间按左端点排序，并分别维护一个指针，假设一个人当前的区间是 $[l_i, r_i]$，另外一个人是 $[l_j, r_j]$，那么这两个区间的交集为 $\max\{0, \, \min\{ r_i, r_j \} - \max\{ l_i, l_j \} \}$。然后如果 $r_i < r_j$，则让 $i$ 加 $1$ 移到下个区间，否则让 $j$ 加 $1$。

  AC 代码如下，时间复杂度为 $O((n+m+q) \sqrt{m})$：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 5, M = 1000;

array<int, 2> a[N];
vector<int> g[N];
int s[N], c[N], last[N];
map<array<int, 2>, int> mp;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i][0] >> a[i][1];
        g[a[i][1]].push_back(a[i][0]);
    }
    for (int i = 1; i <= n; i++) {
        if (g[i].size() < M) continue;
        memset(c, 0, n + 1 << 2);
        for (int j = 1; j <= m; j++) {
            s[j] = s[j - 1] + (a[j][0] - a[j - 1][0]) * !!last[i];
            if (a[j][1] != i && last[a[j][1]]) c[a[j][1]] += s[j] - s[last[a[j][1]]];
            last[a[j][1]] = last[a[j][1]] ? 0 : j;
        }
        for (int j = 1; j <= n; j++) {
            if (j < i) mp[{j, i}] = c[j];
            else if (j > i) mp[{i, j}] = c[j];
        }
    }
    cin >> k;
    while (k--) {
        int x, y;
        cin >> x >> y;
        if (g[x].size() < M && g[y].size() < M) {
            int ret = 0;
            for (int i = 0, j = 0; i < g[x].size() && j < g[y].size(); ) {
                ret += max(0, min(g[x][i + 1], g[y][j + 1]) - max(g[x][i], g[y][j]));
                if (g[x][i + 1] < g[y][j + 1]) i += 2;
                else j += 2;
            }
            cout << ret << '\n';
        }
        else {
            cout << mp[{x, y}] << '\n';
        }
    }
    
    return 0;
}

参考资料

  Editorial - Toyota Programming Contest 2024#8（AtCoder Beginner Contest 365）：https://atcoder.jp/contests/abc365/editorial/10610