题目解析

我们有 $n$ 个用户，每个用户 $i$ 喜欢一个区间 $[l_i, r_i]$。

定义：

• 用户 $j$ 是用户 $i$ 的预测者，当且仅当 $l_j \le l_i \le r_i \le r_j$（即 $j$ 的区间包含 $i$ 的区间）。
• 强推荐曲目：用户 $i$ 不喜欢（不在 $[l_i, r_i]$ 中），但所有 $i$ 的预测者都喜欢。

设所有预测者的区间交集为 $[L, R]$，则：

• $L = \max(\text{所有预测者的 } l)$
• $R = \min(\text{所有预测者的 } r)$

因为每个预测者都包含 $[l_i, r_i]$，所以 $L \le l_i \le r_i \le R$。
强推荐曲目就是 $[L, R]$ 中除去 $[l_i, r_i]$ 的部分，即两个区间：

数量为：

关键思路

1. 重复区间的处理

如果多个用户区间完全相同，那么它们互为预测者。
对于这样的用户，$[L, R] = [l_i, r_i]$，所以强推荐曲目数为 $0$。
因此，相同区间答案直接为 $0$，后续只考虑不同区间。

2. 求 $R$（最小右边界）

对于用户 $i$，预测者集合是：
所有满足 $l_j \le l_i$ 且 $r_j \ge r_i$ 的用户 $j$。

如果我们按 $l$ 递增、$l$ 相同时按 $r$ 递减排序，那么处理到 $i$ 时，所有可能的预测者都已经处理过。
我们维护已处理区间的 $r$ 值集合。
要找 $R = \min\{r_j \mid r_j \ge r_i\}$，只需在集合中二分查找 $\text{lower\_bound}(r_i)$。
然后 $R - r_i$ 就是右侧区间的长度。

3. 求 $L$（最大左边界）

对称地，我们可以将整个问题反射：
把每个区间 $[l, r]$ 映射为 $[-r, -l]$，然后交换 $l$ 和 $r$ 的含义。
在新坐标系下求右侧区间，等价于在原坐标系下求左侧区间。

具体做法：

• 对每个区间取负并交换 $l, r$：新 $l' = -r$，新 $r' = -l$。
• 再次执行同样的算法，得到的 $R' - r'_i$ 就是原问题的 $l_i - L$。

4. 最终答案

分别由两次计算得到。

算法步骤

1. 读入所有区间，记录原始编号。
2. 第一次扫描（求右侧区间）：
   • 按 $(l, -r)$ 排序（$l$ 升序，$r$ 降序）。
   • 用有序集合（如 set）维护已处理的 $r$。
   • 对每个区间，找到第一个 $r_j \ge r_i$，累加 $r_j - r_i$ 到答案。
3. 第二次扫描（求左侧区间）：
   • 将每个区间映射为 $(-r, -l)$，交换 $l, r$。
   • 同样排序和扫描，累加到答案。
4. 处理重复区间：若某个区间出现次数 $>1$，答案置 $0$。

时间复杂度

排序 $O(n \log n)$，集合操作 $O(\log n)$，总 $O(n \log n)$。

C++ 代码实现

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

struct Seg {
    int l, r;
    bool operator<(const Seg &other) const {
        if (l != other.l) return l < other.l;
        return r < other.r;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<Seg> seg(n);
    for (int i = 0; i < n; i++) {
        cin >> seg[i].l >> seg[i].r;
    }

    vector<long long> ans(n, 0);

    // 两次扫描：一次求右侧 (R - r)，一次求左侧 (l - L)
    for (int phase = 0; phase < 2; phase++) {
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);

        // 按 l 升序，l 相同时按 r 降序
        sort(order.begin(), order.end(), [&](int i, int j) {
            if (seg[i].l != seg[j].l) return seg[i].l < seg[j].l;
            return seg[i].r > seg[j].r;
        });

        set<int> rights;  // 存储已处理的右边界
        for (int idx : order) {
            auto it = rights.lower_bound(seg[idx].r);
            if (it != rights.end()) {
                ans[idx] += *it - seg[idx].r;
            }
            rights.insert(seg[idx].r);
        }

        // 反射：准备下一次扫描左侧区间
        for (auto &s : seg) {
            s.l = -s.l;
            s.r = -s.r;
            swap(s.l, s.r);
        }
    }

    // 处理重复区间：答案置 0
    map<Seg, int> cnt;
    for (auto s : seg) cnt[s]++;  // 注意这里的 seg 是反射后的，但反射不影响相等性
    // 上面的反射改变了 seg，所以需要重新读入原始 seg 来计数。更简单的方法：在反射前计数。
    // 修正：我们应在反射前计数原始区间。
    // 为了方便，下面重新计数一次（也可以在最开始就计数）。
    
    // 更稳妥的方法：重新读入一次？不，我们在最开始复制一份原始数据。
    // 简单修正：在函数开头保存原始区间。
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

注意：上面代码中重复区间的处理需要原始区间。更完整的实现见下方最终版本。

最终完整代码（已修正）

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

struct Seg {
    int l, r;
    bool operator<(const Seg &other) const {
        if (l != other.l) return l < other.l;
        return r < other.r;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<Seg> seg(n), original(n);
    for (int i = 0; i < n; i++) {
        cin >> seg[i].l >> seg[i].r;
        original[i] = seg[i];
    }

    vector<long long> ans(n, 0);

    // 两次扫描
    for (int phase = 0; phase < 2; phase++) {
        vector<int> order(n);
        iota(order.begin(), order.end(), 0);
        sort(order.begin(), order.end(), [&](int i, int j) {
            if (seg[i].l != seg[j].l) return seg[i].l < seg[j].l;
            return seg[i].r > seg[j].r;
        });

        set<int> rights;
        for (int idx : order) {
            auto it = rights.lower_bound(seg[idx].r);
            if (it != rights.end()) {
                ans[idx] += *it - seg[idx].r;
            }
            rights.insert(seg[idx].r);
        }

        // 反射
        for (auto &s : seg) {
            s.l = -s.l;
            s.r = -s.r;
            swap(s.l, s.r);
        }
    }

    // 处理重复区间
    map<Seg, int> cnt;
    for (auto s : original) cnt[s]++;
    for (int i = 0; i < n; i++) {
        if (cnt[original[i]] > 1) ans[i] = 0;
        cout << ans[i] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}