2022年9月月赛乙组 T1.区间交集（二）

2022年9月月赛乙组 T1.区间交集（二）
内存限制: 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，也最好使用快读。

#include<bits/stdc++.h>
using namespace std;
const int N=300010;
struct Node{
	int l,r;
	friend bool operator<(Node a,Node b){
		if(a.l!=b.l) return a.l<b.l;
		else return a.r<b.r;
	}
}node[N];
inline int read(){ //整数快读
	int x=0;
	char c=0;
	while(c<'0'||c>'9') c=getchar();
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';c=getchar();
	}
	return x;
}
int main()
{
	int n=read();
	for(int i=1;i<=n;i++){
		node[i].l=read();node[i].r=read();
	}
	sort(node+1,node+n+1);
	long long ans=0;//注意数据类型
	for(int i=1;i<=n;i++){
		//每次找到有多少个j>i满足第j个区间和第i个区间相交(node[j].l<=node[i].r)
		int lf=i,rt=n;//用二分法找满足条件的极右值(最大值)
		while(lf<rt){
			int mid=(lf+rt+1)>>1;
			if(node[mid].l>node[i].r)rt=mid-1;
			else lf=mid;
		}
		ans+=(rt-i);
	}
	cout<<ans;
	return 0;
}

最后

以上就是超级期待为你收集整理的2022年9月月赛乙组 T1.区间交集（二）的全部内容，希望文章能够帮你解决2022年9月月赛乙组 T1.区间交集（二）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。