D - Many Segments 2(AtCoder Beginner Contest 377)
题目链接:
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;
}