题解 | #值周#

首先试的差分，不过前缀和更省事一点
下面是差分代码和前缀和代码

#include<algorithm>
#include<cmath>
#include<numeric>
#include<vector>
typedef long long ll;
using namespace std;

struct s{
	int x,y;
}node[1000005];
bool cmp(s a,s b)
{
	return a.x < b.x;
}
int main()
{
	int l, m;
	cin >> l >> m;
	for (int i = 1; i <= m; i++)
	{
		cin >> node[i].x >> node[i].y;
	}
	sort(node + 1, node + m+1,cmp);
	ll ans = 0;
	int max = -1;
	for (int i = 1; i <= m; i++)
	{
		if (node[i].x <= max)
		{
			if (node[i].y > max)
			{
				ans += node[i].y - max;
				max = node[i].y;
			}
		}
		else
		{
			ans += node[i].y - node[i].x + 1;
			max = node[i].y;
		}
	}
	cout << l+1-ans << endl;
	return 0;
}

前缀和代码：

#include<algorithm>
#include<cmath>
#include<numeric>
#include<vector>
typedef long long ll;
using namespace std;

struct s{
	int x,y;
}node[1000005];
bool cmp(s a,s b)
{
	return a.x < b.x;
}
int main()
{
	int l, m;
	cin >> l >> m;
	int s[100000005] = { 0 };
	for (int i = 1; i <= m; i++)
	{
		int a, b;
		cin >> a >> b;
		s[a] -= 1;
		s[b+1] += 1;
	}
	int ans = 0;
	if (s[0] == 0) ans = 1;
	for (int i = 1; i <= l; i++)
	{
		s[i] += s[i - 1];
		if (s[i] == 0) ans++;
	}
	cout << ans;
	return 0;
}