题目描述

难度分:$1900$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和$n$个闭区间，每个闭区间输入两个数$L$和$R(1 \leq L \leq R \leq 10^9)$。

对于每个区间$[L,R]$，设包含$[L,R]$的其他区间的交集为$S$，输出$S$中的整数的个数减去$[L,R]$中的整数的个数。如果没有包含$[L,R]$的其他区间，输出$0$。

输入样例

4
3
3 8
2 5
4 5
2
42 42
1 1000000000
3
42 42
1 1000000000
42 42
6
1 10
3 10
3 7
5 7
4 4
1 2

输出样例

0
0
1
999999999
0
0
0
0
0
2
3
2
4
8

算法

双指针+线段树

将所有区间$[l,r]$添加一个编号的维度变为$[l,r,i]$，组成一个$intervals$数组，然后离线来做。

把$intervals$按照区间左端点升序排列（如果左端点相同按照右端点降序，保证大区间先遍历到），然后遍历所有区间。当遍历到区间$intervals[i]=[l_i,r_i,i]$时，左端点$\lt l_i$的区间已经都遍历过了，我们希望知道这些区间里面，右端点$\geq r_i$的最小右端点是哪个（可能不存在）？将这个右端点记为$R[i]$，考虑到$l_i$和$r_i$的取值范围很大，可以对区间右端点开一个权值线段树，线段树的索引是端点值离散化之后的结果，索引上存的值是端点真正的值。那么遍历到$[l_i,r_i,i]$时，查询一下线段树$[pos(r_i),len]$上的最小值即可，其中$pos(x)$表示$x$离散化后的值，$len$表示线段树的索引长度，和离散化后有多少个坐标有关。求完了$intervals[i]$的信息$R[i]$，再把$r_i$更新在线段树$pos(r_i)$位置上。

得到了$R[i]$，再将$intervals$按照降序排列（如果右端点相同，按照左端点升序，确保大区间先遍历到），同样的方法求$L[i]$，它表示右端点$\geq r_i$的区间中，最大的左端点（可能不存在），通过在线段树$[1,pos(l_i)]$上查询获得。

预处理出了$L$和$R$两个信息，在$L[i]$和$R[i]$都存在的情况下，区间$[l_i,r_i]$的答案就是$L[i]-R[i]-(l_i-r_i)$；区间不存在答案就是$0$。

还需要注意一点，如果区间$[l_i,r_i]$在$intervals$中不止出现一次，那么这个区间的答案肯定也是$0$，因为所有包含它的区间交集肯定还是它自己。用一个$map$记录所有区间的频数就可以高效判断这个。

复杂度分析

时间复杂度

离散化区间端点需要对所有端点排序，时间复杂度为$O(nlog_2n)$；对$intervals$排序时间复杂度为$O(nlog_2n)$；每个$i$求$L[i]$和$R[i]$的时候，需要对线段树进行查询和修改操作，每个索引的时间复杂度为$O(log_2n)$，总的时间复杂度为$O(nlog_2n)$。最后每个索引求答案是$O(n)$的，并非整个算法的瓶颈。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

开辟了$L$、$R$两个数组、离散化的无重端点数组、离散化的映射表、区间频数映射表，以及线段树空间。它们都是线性空间，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 400010, INF = 0x3f3f3f3f;

int T, n;
int ans[N], L[N], R[N];

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

class SegmentTree {
public:
    struct Info {
        int l, r, mx, mn;
        Info() {}
        Info(int left, int right, int val): l(left), r(right), mn(val), mx(val) {}
    } seg[N<<2];

    explicit SegmentTree() {}

    void build(int u, int l, int r, int v) {
        if(l == r) {
            seg[u] = Info(l, r, v);
        }else {
            int mid = l + r >> 1;
            build(u<<1, l, mid, v);
            build(u<<1|1, mid + 1, r, v);
            pushup(u);
        }
    }

    void modify(int pos, int val) {
        modify(1, pos, val);
    }

    Info query(int l, int r) {
        if(l > r) return Info(0, 0, 0);
        return query(1, l, r);
    }

private:
    void modify(int u, int pos, int val) {
        if(seg[u].l == pos && seg[u].r == pos) {
            seg[u] = Info(pos, pos, val);
        }else {
            int mid = seg[u].l + seg[u].r >> 1;
            if(pos <= mid) modify(u<<1, pos, val);
            else modify(u<<1|1, pos, val);
            pushup(u);
        }
    }

    Info query(int u, int l, int r) {
        if(l <= seg[u].l && seg[u].r <= r) return seg[u];
        int mid = seg[u].l + seg[u].r >> 1;
        if(r <= mid) {
            return query(u<<1, l, r);
        }else if(mid < l) {
            return query(u<<1|1, l, r);
        }else {
            return merge(query(u<<1, l, r), query(u<<1|1, l, r));
        }
    }

    void pushup(int u) {
        seg[u] = merge(seg[u<<1], seg[u<<1|1]);
    }

    Info merge(const Info& lchild, const Info& rchild) {
        Info info;
        info.l = lchild.l;
        info.r = rchild.r;
        info.mn = min(lchild.mn, rchild.mn);
        info.mx = max(lchild.mx, rchild.mx);
        return info;
    }
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        vector<int> pos;
        map<PII, int> counter;
        vector<array<int, 3>> intervals;
        for(int i = 1; i <= n; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            pos.push_back(l);
            pos.push_back(r);
            intervals.push_back({l, r, i});
            counter[{l, r}]++;
        }
        sort(pos.begin(), pos.end());
        pos.erase(unique(pos.begin(), pos.end()), pos.end());
        int sz = pos.size();
        unordered_map<int, int, custom_hash> val2pos;
        for(int i = 0; i < sz; i++) {
            val2pos[pos[i]] = i + 1;
        }
        SegmentTree seg;
        seg.build(1, 1, sz, INF);
        sort(intervals.begin(), intervals.end(), [&](auto&a, auto&b) {
            return a[0] != b[0]? a[0] < b[0]: a[1] > b[1];
        });
        for(int i = 1; i <= n; i++) {
            int right = val2pos[intervals[i - 1][1]], index = intervals[i - 1][2];
            int high = seg.query(right, sz).mn;
            R[index] = high == INF? 0: high;
            seg.modify(right, intervals[i - 1][1]);
        }
        seg.build(1, 1, sz, 0);
        sort(intervals.begin(), intervals.end(), [&](auto&a, auto&b) {
            return a[1] != b[1]? a[1] > b[1]: a[0] < b[0];
        });
        for(int i = 1; i <= n; i++) {
            int left = val2pos[intervals[i - 1][0]], index = intervals[i - 1][2];
            int low = seg.query(1, left).mx;
            L[index] = low == 0? INF: low;
            seg.modify(left, intervals[i - 1][0]);
        }
        for(int i = 1; i <= n; i++) {
            int index = intervals[i - 1][2], left = intervals[i - 1][0], right = intervals[i - 1][1];
            if(counter[{left, right}] > 1) {
                ans[index] = 0;
            }else {
                int low = L[index], high = R[index];
                if(low <= high) {
                    ans[index] = high - low - (right - left);
                }else {
                    ans[index] = 0;
                }
            }
        }
        for(int i = 1; i <= n; i++) {
            printf("%d\n", ans[i]);
        }
    }
    return 0;
}