ABC 377

D. Many Segments 2

        这也是一道采用倒序求解的题，但为什么会想到倒序做呢？先来看这道题。

        首先思考到，对于枚举的 i（作为答案区间的左端点），需要找到所有左端点在 i 右边的区间中，右端点的最小值。

        如果正序做，i 从 1 开始，那在最开始的时候就会有很多区间的左端点在 i 的右边。随着 i 增大，符合条件的区间越来越少。

        如果倒序做，i 从 n 开始，最开始没有区间符合条件，没有左端点在 i 右边的区间，随着 i 不断减小，会有越来越多的区间要被纳入 i 的右侧，有可能会被全覆盖。

        由此观之，发现正序是从多到少，递减的过程，一开始就会有很多变量符合条件。倒序是从少到多，递增的过程，不断有变量开始符合条件。

        是因为要过程递增，所以要去考虑倒序求解。

        对于一个区间的左右端点固定的情况，map 直接去映射左端点对应的右端点。i 向左移的时候，一旦有新的区间的左端点在 i 右边（包括 i），就去看所有右端点的最小值是否能更新。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;int T, n, m, cnt, ans;
map<int, int> mp;signed main()
{cin >> n >> m;int t = 0;for (int i = 1; i <= n; i ++){int l, r;cin >> l >> r;if (mp.count(l) == 0)mp[l] = r;elsemp[l] = min(mp[l], r);}int R = m;for (int L = m; L >= 1; L --){if (mp.count(L) != 0)R = min(R, mp[L] - 1);ans += max(R - L + 1, t);}cout << ans;return 0;
}