ABC 355

D. Intersecting Intervals

        首先思考两个区间相交会有哪些情况：有两种左右端点包含，一种大区间包含小区间。

        但是反过来思考，两个区间不相交只会有两种情况：Ri < Lj 和 Rj < Li。非常典型的逆向思考

         对左右端点升序排序后，枚举右端点，找到大于它的第一个左端点，后面所有的都符合。

        n 个区间选两个共 n * ( n – 1 ) / 2，减掉两两不相交的数量，就是答案。注意总数不是 n。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 5, INF = 1e18;

int T, n, cnt, tot, ans, l[N], r[N];

signed main()
{
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> l[i] >> r[i];
sort(l + 1, l + n + 1);
sort(r + 1, r + n + 1);
for (int i = 1; i <= n; i ++)
{
int pos = upper_bound(l + 1, l + n + 1, r[i]) – l;
tot += n – pos + 1;
}
ans = n * (n – 1) / 2 – tot;
cout << ans;
return 0;
}