内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个数轴上的闭区间，请统计有多少对区间的交集不是空集。
输入格式
第一行：一个整数 nn；
接下来 n 行：每行两个整数 ai 与 bi ，表示一个闭区间的左端点与右端点。
输出格式
单个整数：表示有多少对区间的交集不是空集。
数据范围
对于 30% 的数据，1≤n≤5,000；
对于 60% 的数据，1≤n≤20,000；
对于 100% 的数据，1≤n≤300,000；
1≤ai≤bi≤1,000,000；
样例数据
输入:
3
1 10
1 4
5 12
输出:
2
输入:
2
1 2
2 3
输出:
1
说明:
两个闭区间的交可能只有一个数字，在这种情况下，也是符合非空要求的。
题目解析：
直接判断区间是否有交集其实比较麻烦。
如果已知左端点的大小顺序，再判断是否有交集会变得很简单。
对所有区间，按照左端点从小到大进行排序，那么我们对i区间，
考虑i+1~n个区间，这些区间的左端点是否小于等于i的右端点即可。
为提升效率我们可以用二分法进行优化。
读入数据的规模为6*10^5，也最好使用快读。
1. #include<bits/stdc++.h> 2. using namespace std; 3. const int N=300010; 4. struct Node{ 5. int l,r; 6. friend bool operator<(Node a,Node b){ 7. if(a.l!=b.l) return a.l<b.l; 8. else return a.r<b.r; 9. } 10. }node[N]; 11. inline int read(){ //整数快读 12. int x=0; 13. char c=0; 14. while(c<'0'||c>'9') c=getchar(); 15. while(c>='0'&&c<='9') { 16. x=x*10+c-'0';c=getchar(); 17. } 18. return x; 19. } 20. int main() 21. { 22. int n=read(); 23. for(int i=1;i<=n;i++){ 24. node[i].l=read();node[i].r=read(); 25. } 26. sort(node+1,node+n+1); 27. long long ans=0;//注意数据类型 28. for(int i=1;i<=n;i++){ 29. //每次找到有多少个j>i满足第j个区间和第i个区间相交(node[j].l<=node[i].r) 30. int lf=i,rt=n;//用二分法找满足条件的极右值(最大值) 31. while(lf<rt){ 32. int mid=(lf+rt+1)>>1; 33. if(node[mid].l>node[i].r)rt=mid-1; 34. else lf=mid; 35. } 36. ans+=(rt-i); 37. } 38. cout<<ans; 39. return 0; 40. }
