Luogu P2082 区间覆盖（加强版）

链接
难度： 普及/提高-

有 \(n\) 个区间 \([s_i,t_i]\)，求被这 \(n\) 个区间覆盖的长度。

数据范围：\(n\le 10^5, 1\le s_i<t_i\le10^17\)。

把每个区间都换成一组匹配的括号，考虑以下序列（不同的括号代表的是不同的区间）：

..[..(].{.)..}..

发现这个部分被覆盖的距离实际就是 [ 到 } 的距离。

所以每次当遇到一个括号序列的开头时，记录 \(st=x\)，每当一个括号序列结束，记录 \(ed=y\)，这一部分对答案的贡献便是 \(ed-st+1\)。

由于 \(s_i,t_i\) 过大所以需要离散化。

// Problem: P2082 区间覆盖（加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2082
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

# include <bits/stdc++.h>
using namespace std;
map <long long, int> mp;
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int n;
	cin >> n;
	for (int i = 1, a, b; i <= n; ++ i) {
		cin >> a >> b;
		++ mp [a], -- mp [b];
	}
	long long ans = 0, last;
	int tot = 0;
	for (pair <int, int> it : mp) {
		if (! tot) {
			last = it .first;
		}// 开头
		tot += it .second;
		if (! tot) {
			ans += it .first - last + 1;
		}// 结尾
	}
	cout << ans;
	return 0;
}