题目描述
给定 n 个数轴上的闭区间，请统计有多少对区间的交集不是空集。
输入格式
第一行：一个整数 n；
接下来 n 行：每行两个整数 a_i与 b_i ，表示一个闭区间的左端点与右端点。
输出格式
单个整数：表示有多少对区间的交集不是空集。
数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤20,000；
对于 100% 的数据，1≤n≤300,000；
1≤ai≤bi≤1,000,000；
【题解】
1、暴力枚举的方式
统计多少对满足题意，暴力枚举，N*N的时间复杂度。通过for 枚举 i ：1-n，j:i+1 -n，统计有多少交集。但这种只能得大约60分。
2、优化思想：
假设 现有区间[x,y] 和[a,b]。计算这两个区间是否交集，可以考虑若 各区间左端点有序，那么判断这两个区间是否有交集，只需要判断 y 和 a 的大小关系即可，若 y > a，则这两个区间必有交集。
对全部区间可以这样考虑：
将所有区间左端点按照从小到大排序，那么对第i个区间，考虑第i+1 ~ n个区间，由于这些区间中左端点均大于第i个区间，因此只需要判断 y（第i个区间右端点） 与这些区间的左端点关系即可。（二分）
程序代码
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int n,ans;
struct Sec
{
int l,r;
}a[300010];
bool cmp(Sec s1,Sec s2)
{
return s1.l < s2.l || s1.l == s2.l && s1.r < s2.r;
}
int check(int x)
{
int l = 1,r = n,mid;
int ret = n + 1;
while(l <= r)
{
mid = l + r >> 1;
if(a[mid].l > x)
{
ret = mid;
r = mid - 1;
}
else l = mid + 1;
}
return ret;
}
signed main()
{
cin >> n;
for(int i = 1;i <= n;i ++) scanf("%d%d",&a[i].l,&a[i].r);
sort(a + 1,a + n + 1,cmp);
for(int i = 1;i <= n;i ++) ans += check(a[i].r) - i - 1;
cout << ans << endl;
return 0;
}