当前位置：首页 > article >正文

D - Many Segments 2（AtCoder Beginner Contest 377)

article 2024/10/28 4:48:40

题目链接：

D - Many Segments 2 (atcoder.jp)

题目描述：

数据范围：

样例输入：

2 4
1 2
3 4

样例输出：

5

样例解释：

分析：

题目让找合法的区间，但是合法的话去要去枚举左右端点，时间复杂度O(n * n), 会TLE的。间接的去做会好点。

总的（m * (m + 1) / 2）减去不合法的区间 = 合法的区间。

不合法的区间就是包括任意一个读入的区间(l[i], r[i])。枚举1到m，作为不合法区间的左端点，假如这个i的后面区间里面，离i最近的右端点是r[i], 那么由这个左端点提供的不合法的区间个数就是 m - r[i] + 1。为什么求最近的呢？下图：

但是问题是，我怎么知道位置i右边区间里面最左边的r呢？

从后往前枚举，用hou数组去记录，那么找的时候就可以O(1)的时间复杂度去找到。

这里我用了fill去填充了hou数组，第一个参数是数组起始地址，第二个参数是数组结束地址+1，(左闭右开) 第三个参数是填充的值。只要值为200010,就表示当前点的右边是没有区间的，那么就不存在违法区间。

代码：

#include<bits/stdc++.h>
#define int long long

using namespace std;

map<int, int>mp;
int hou[200010];


signed main() {
	int n, m;
	cin >> n >> m;
	int ret = m * (m + 1) / 2;
	int a[m + 10];
	memset(a, 0, sizeof a); 
	int cnt = 0;
	set<int>se;
	
	for(int i = 1; i <= n; i ++ ) {
		int l, r;
		cin >> l >> r;
		if(mp[l] == 0) {
			mp[l] = r;
		}
		mp[l] = min(mp[l], r);//知道当前最小的 
		se.insert(l);
	}
	fill(hou, hou + m + 10, 200010);
	
	//hou[i]表示的是 i后面区间 里面 r最靠左的。 
	for(int i = m ; i >= 1; i -- ) {
		if(mp[i]) {
			//取最小的 
			hou[i] = min(hou[i + 1], mp[i]);
		} else {//延续下去 
			hou[i] = hou[i + 1];
		}	
	}
	for(int i : se) {
		a[ ++ cnt] = i;
	}
	for(int i = 1; i <= m; i ++ ) {
		if(hou[i] !=  200010) {
			ret -= (m - hou[i] + 1);
		} 
	}
	cout << ret << endl;
	return 0;
}