思路是把询问都挂在在岗时间段数更多的那个员工上，然后按每个员工在岗时间段数是否 $\ge \sqrt{n}$ 分成两类。

段数 $\ge \sqrt{n}$ 的不会超过 $\sqrt{n}$ 个（视作 $n,\ m,\ Q$ 同级），那么我们对每个这样的员工都求一下与其他的 $n - 1$ 个员工的共存时间（这里要把 $n-1$ 个员工放在一起做，不然复杂度就变成 $O(n\sqrt{n} \times \sqrt{n}) = O(n^2)$ 了），那么单个员工时间复杂度为 $O(n)$，这部分总复杂度为 $O(n\sqrt{n})$。

段数 $< \sqrt{n}$ 的两个员工，每次计算的复杂度也是 $O(\sqrt{n})$ 的，则直接计算这些询问德总复杂度也不会超过 $O(n\sqrt{n})$。

所以我这篇代码的总体时间复杂度不会超过 $O(n\sqrt{n})$，应该可以在本题时限与范围下通过。

但是我却 TLE 了 20 个点，是常数原因还是哪里的复杂度不正确？

代码：

#pragma GCC optimize(3)
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

const int N = 2e5 + 10;
using pii = pair<int, int>;
#define mp make_pair
#define sz(A) int(A.size())
#define fi first
#define se second

int n, m, Q, last[N];
vector<pii> a[N];
int calc(int x, int y){
    int ans = 0;
    for(int i = 0, j = 0; i < sz(a[x]) && j < sz(a[y]); i++){
        auto [lx, rx] = a[x][i];
        while(j < sz(a[y]) && a[y][j].fi < a[x][i].se){
            auto [ly, ry] = a[y][j];
            ans += max(0, min(rx, ry) - max(lx, ly));
            j++;
        }
        if(j > 0) j--;
    }
    return ans;
}

vector<int> A;
int p[N], val[N];
vector<pii> query[N];
int ans[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    while(m--){
        int t, p;
        cin >> t >> p;
        if(last[p] == 0) last[p] = t;
        else{
            a[p].push_back(mp(last[p], t));
            last[p] = 0;
        }
    }
    cin >> Q;
    for(int i = 1; i <= Q; i++){
        int x, y;
        cin >> x >> y;
        if(sz(a[x]) < sz(a[y])) swap(x, y);
        query[x].push_back(mp(y, i));
    }
    int B = sqrt(n);
    for(int i = 1; i <= n; i++){
        if(sz(a[i]) >= B) A.push_back(i);
        else{
            for(auto [y, id]: query[i]) ans[id] = calc(i, y);
        }
    }
    for(int x: A){
        for(int i = 1; i <= n; i++) p[i] = 0, val[i] = 0;
        for(int i = 0; i < sz(a[x]); i++){
            auto [lx, rx] = a[x][i];
            for(int j = 1; j <= n; j++){
                if(j == x) continue;
                while(p[j] < sz(a[j]) && a[j][p[j]].fi < rx){
                    auto [ly, ry] = a[j][p[j]];
                    val[j] += max(0, min(rx, ry) - max(lx, ly));
                    p[j]++;
                }
                if(p[j] > 0) p[j]--;
            }
        }
        for(auto [y, id]: query[x]) ans[id] = val[y];
    }
    for(int i = 1; i <= Q; i++) cout << ans[i] << '\n';
    return 0;
}