题目翻译

有 $n$ 个人，给定 $m$ 个信息，第 $i$ 条表示 $t_i$ 时刻人 $p_i$ 进 / 出了房间。

进还是出由之前的状态决定。保证最后所有人都是出的。

现在给定 $q$ 个询问，查询 $a,b$ 表示 $a$ 在房间和 $b$ 在房间的时间的交集大小。

$2\leq n,m\leq 2\times 10^5$，$1\leq p_i,a,b\leq n$，$1\leq t_i\leq 10^9$，保证 $t_i$ 严格递增。

题目思路

后文复杂度不严格区分 $n$ 与 $m$ 还有 $q$。默认都是 $n$ 量级的。

我们先把进出房间的时刻看成线段的两个端点，线段就是这个人在房间里的时间。

那么这个题转化成问两个人线段的交集大小。

设 $cnt_i$ 表示第 $i$ 个人的线段个数，我们可以得到 $\mathcal O(\sum\limits_{i=1}^n cnt_i)=\mathcal O(n)$。

$n$ 个人 $n$ 条线段，不难想到是根号分治，线段数量 $\gt B$ 的人数量是 $\leq \frac n B$ 的。

根据这个，我们把人分为大人和小人。根据这个讨论怎么做。

• 两个小人

  那么我们把这些线段合并，记 $lst_{0/1}$ 表示 $a$ 或 $b$ 上一个左端点在哪里。往序列里扔每个人的端点，记录三个值 $t,o,p$ 表示时间刻，是左端点还是右端点，是 $a$ 还是 $b$ 的时间刻。

  如果找到左端点更新 $lst$。找到右端点算 $t-\max\{lst_0,lst_1\}$ 就是这一段线段的答案。

  把每个人的线段加进来的过程，需要排序。但是我们如果本来线段就是有序存放的，我们归并即可。两个有序地数组归并到一起只需要维护两个指针移动。这样这部分就是 $\mathcal O(\sqrt n)$ 时间内解决。

• 一大一小

  不妨设 $a$ 是小人 $b$ 是大人。

  单独分这一类不是很必要，但这是两个大人处理的基础。

  枚举小人的区间，那么我们就要支持查询区间内 $b$ 的时间有多长。

  端点数量是 $\mathcal O(n)$ 的，我们设 $sum_{i,j}$ 表示第 $i$ 个大人的前 $j$ 个时刻（时刻是 $10^9$ 级别的，但是可以离散化成 $n$ 级别的）有多少时间在房间里。这个 $sum$ 提前预处理出来，处理方式很简单，不细说了。

  通过前缀和减一下就能得到我们区间内 $b_i$ 的时间数量。

  这一段复杂度 $\mathcal O(\sqrt n)$。

• 两个大人

  设 $ans_{i,j}$ 表示第 $i$ 个大人和第 $j$ 个大人的答案。

  枚举第 $i$ 个大人，枚举第 $j$ 个大人。由于 $\mathcal O(\sum\limits_{i=1}^n cnt_i)=\mathcal O(n)$，那么所有可能的第 $j$ 个大人的线段总数是 $\mathcal O(n)$ 的。所以暴力预处理 $ans_{i,j}$ 复杂度就是正确的。

  事实上，一大一小可以和两个大人合并在一起， 设 $ans_{i,j}$ 表示第 $i$ 个大人和第 $j$ 个人的答案。 但是赛时想到了一大一小的做法就先敲上了，不改了。

所以我们在 $\mathcal O(n\sqrt n)$ 的时间内完成了这个问题。

实现的时候注意一些小问题，比如要提前离散化信息，两个小人的处理归并合并。这些多的 $\log$ 都可以简单优化掉，这里不细说了。

完整代码

AT submission 56309131

成为了全场倒数第二个过 G 的。

一开始写的 $\mathcal O(n\sqrt n\log n)$ 的 TLE 了 $2$ 个点。但是有人 $\mathcal O(n\sqrt n\log n)$ 卡过去了，可能我写的常数有点大。

#include <bits/stdc++.h>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
char buf[1000000], *p1 = buf, *p2 = buf;
template <typename T>
void read(T &x)
{
    x = 0;
    int f = 1;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-')
            f = -f;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= f;
}
template <typename T, typename... Args>
void read(T &x, Args &...y)
{
    read(x);
    read(y...);
}
template <class T>
void write(T x)
{
    static int stk[30];
    if (x < 0)
        putchar('-'), x = -x;
    int top = 0;
    do
    {
        stk[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        putchar(stk[--top] + '0');
}
template <class T>
void write(T x, char lastChar) { write(x), putchar(lastChar); }
const int inf = 2e9;
const int B = 300;
int n, m;
int Q;
array<int, 2> a[200020];
vector<array<int, 2>> vec[200020];
bool in[200020];
int lst[200020];
int sum[700][200020];
int lsh[200020];
int id[200020], tot;
bool hav[200020];
int aa[700][700];
vector<int> big;
unordered_map<int, int> mp;
int main()
{
    read(n, m);
    for (int i = 1; i <= m; i++)
    {
        read(a[i][0], a[i][1]);
        if (in[a[i][1]])
            vec[a[i][1]].push_back({lst[a[i][1]], a[i][0]});
        else
            lst[a[i][1]] = a[i][0];
        in[a[i][1]] ^= 1;
        mp[a[i][0]] = i;
    }
    big.push_back(0);
    for (int i = 1; i <= n; i++)
    {
        if (vec[i].size() <= B)
            continue;
        big.push_back(i);
        id[i] = ++tot;
        memset(hav, 0, sizeof(hav));
        for (auto [l, r] : vec[i])
        {
            for (int j = mp[l] + 1, ed = mp[r]; j <= ed; j++)
                hav[j] = 1;
        }
        for (int i = 1; i <= m; i++)
        {
            if (hav[i])
                sum[tot][i] = a[i][0] - a[i - 1][0];
        }
        for (int i = 1; i <= m; i++)
            sum[tot][i] += sum[tot][i - 1];
    }
    for (int i = 1; i < big.size(); i++)
    {
        for (int j = 1; j < big.size(); j++)
        {
            if (i == j)
                continue;
            int y = big[j];
            for (auto [l, r] : vec[y])
                aa[i][j] += sum[i][mp[r]] - sum[i][mp[l]];
        }
    }
    read(Q);
    while (Q--)
    {
        int x, y;
        read(x, y);
        if (vec[x].size() > vec[y].size())
            swap(x, y);
        if (vec[y].size() <= B) // 小小
        {
            vector<array<int, 3>> u, v;
            int i = 0, j = 0;
            for (auto [l, r] : vec[x])
            {
                u.push_back({l, 0, 0});
                u.push_back({r, 1, 0});
            }
            for (auto [l, r] : vec[y])
            {
                while (i < u.size() && u[i][0] <= l)
                    v.push_back(u[i]), i++;
                v.push_back({l, 0, 1});
                while (i < u.size() && u[i][0] <= r)
                    v.push_back(u[i]), i++;
                v.push_back({r, 1, 1});
            }
            int lst[2] = {inf, inf};
            int ans = 0;
            for (auto [t, o, p] : v)
            {
                if (o == 1)
                {
                    if (lst[0] < inf && lst[1] < inf)
                        ans += t - max(lst[0], lst[1]);
                    lst[p] = inf;
                }
                else
                {
                    lst[p] = t;
                }
            }
            write(ans, '\n');
        }
        else if (vec[x].size() <= B) // 小大
        {
            int j = id[y];
            int ans = 0;
            for (auto [l, r] : vec[x])
                ans += sum[j][mp[r]] - sum[j][mp[l]];
            write(ans, '\n');
        }
        else // 大大
        {
            write(aa[id[x]][id[y]], '\n');
        }
    }
    return 0;
}