思路

序言

其实这道题实现起来并不难，只是思路有些不好想。

说说思路

我们定义一个 $a$ 数组，$a_r$ 表示以 $r$ 为右端点， $l+1$ 的最大值。再用一个 $ans$ 记录答案，我们使 $l=1$ ，在 $1\le r\le m$ 中，不断更新 $l=max(l,a[r])$ ，则 $ans+=r-l+1$ 。

解释一下吧

$a_r$为什么要这么预处理？

$a_r$ 表示为左端点必须至少为 $a_r$ ，才能避免包含任何以 $r$ 为右端点的给定区间。因为如果左端点不大于 $l$ ，那么区间 $[l, r]$ 就会被包含。取 $l+1$ 是为了得到严格大于所有左端点的最小值，取最大值是为了处理多个区间重叠的情况,保证合法。

为什么 $ans$ 要这样算 ？

因为要保证不要重复计算情况数。使 $l = max(l, a[r])$ ，这样 $l$ 就保证了所有右端点不大于 $r$ 的给定区间都不会被包含。

复杂度分析

• 时间复杂度：预处理读入 $n$ 个区间，更新 $a$ 数组，$O(n)$；扫描右端点 $m$ 次，每次 $O(1)$，总复杂度 $O(n + m)$。
• 空间复杂度：$a$ 数组大小为 $m+1$，即 $O(m)$。

代码实现

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

int n, m, a[200005];
long long ans;

int main() {
    cin >> n >> m;
    for (int i = 1, l, r; i <= n; i++) {
        cin >> l >> r;
        a[r] = max(a[r], l + 1);  // 记录以 r 为右端点的最大左端点+1
    }
    for (int r = 1, l = 1; r <= m; r++) {
        l = max(l, a[r]);          // 更新左端点下限
        ans += r - l + 1;          // 累加以 r 为右端点的合法区间个数
    }
    cout << ans << endl;
    return 0;
}

提示

十年 $OI$ 一场空，不开 long long 见祖宗。