T1：区间交集（二）
这种统计有多少对满足题意，首先想下暴力
\(O(n^2)\) 复杂度
正解：
判断区间是否有交集，其实比较麻烦，怎么简单判断？
- 如果已知左端点的大小顺序，那么判断是否有交集会很简单
- 由此可以得到一个思路，即对所有区间按照左端点从小到大排序，那么我们对于第 \(i\) 个区间考虑第 \(i+1 \sim n\) 个区间，这些区间的左端点都比第 \(i\) 个区间的左端点大，那么只需判断右端点 \(y\) 和这些左端点的关系（二分）
代码实现
#include <bits/extc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
struct Interval {
int l, r;
Interval(){}
Interval(int l, int r): l(l), r(r) {}
bool operator<(const Interval& o) const {
return l < o.l;
}
};
inline int read() {
int x = 0;
char c;
while (c < '0' or c > '9') c = getchar();
while ('0' <= c and c <= '9') {
x = x*10+c-'0';
c = getchar();
}
return x;
}
int main() {
int n = read();
vector<Interval> intervals(n);
rep(i, n) {
intervals[i].l = read();
intervals[i].r = read();
}
sort(intervals.begin(), intervals.end());
ll ans = 0;
rep(i, n) {
// 每次找出有多少个 j>i 满足第 j 个区间和第 i 个区间相交 （intervals[j].l <= intervals[i].r）
int ac = i, wa = n;
while (abs(ac-wa) > 1) {
int wj = (ac+wa)/2;
if (intervals[wj].l <= intervals[i].r) ac = wj; else wa = wj;
}
ans += ac-i;
}
cout << ans << '\n';
return 0;
}