背景

影几欺哄了众生了
天以外——
月儿何曾圆缺

描述

有些东西就如同月光的魔法一般.
Luke是爱着vijos的.
他想为自己心爱的东西画些什么.
就画N个圆吧.
把它们的圆心都固定在x轴上.
圆与圆.
为了爱,两两不能相交.
为了爱,它们可以互相贴在一起.
内切或外切,都是允许的.
vijos的美丽,在于人心.
vijos的孩子们,一定能告诉大家:Luke画的圆究竟把平面分割成了多少块?
月光恬美地洒在大地上.
Luke知道,如果什么都不画,平面就只有一块.多美呢!
Luke知道,只画一个圆,平面就分成了两块.也很美呢!
但Luke还是要多画一些的,因为他真的深爱着vijos呢.

格式

输入格式

输入数据第一行:输出一个整数N,1<=N<=300,000.表示圆的个数.
之后N行,每一行有2个整数,x[i]和r[i]表示圆心固定在x[i]的位置,半径为r[i].
-1,000,000,000<=x[i]<=1,000,000,000
1<=r[i]<=1,000,000,000
所有圆都是唯一的,不会出现重叠.

输出格式

输出只有一行,要求输出平面被分割成了多少块.

样例1

样例输入1

2
1 3
5 1

样例输出1

3

样例2

样例输入2

3
2 2
1 1
3 1

样例输出2

5

样例3

样例输入3

4
7 5
-9 11
11 9
0 20

样例输出3

6

限制

对于40%的数据:
N<=5000.
对于100%的数据:
1<=N<=300,000;-1,000,000,000<=x[i]<=1,000,000,000;1<=r[i]<=1,000,000,000
 

题解：

乍一看，我们可能会觉得这是一个线段树的题，但我们发现，其实它只要最后的结果，所以我们用不着线段树，我们可以模拟！！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int vis[1300030];
struct qer
{
	int l, r, len;
}d[1300030];
struct lsh
{
	int num, id;
}ls[1600030];
struct sss
{
	int vi, l, r;
}used[1300030];
bool cmp(lsh a, lsh b)
{
	return a.num < b.num;
}
bool cmmp(qer a, qer b)
{
	return a.len < b.len;
}
int main()
{
	int n;
	cin >> n;
	ls[0].num = -2147483600;
	for (int i = 1; i <= n; i++)
	{
		int x, r;
		scanf("%d%d", &x, &r);
		ls[i*2-1].num = x-r;
		ls[i*2].num = x+r;
		ls[i*2-1].id = i;
		ls[i*2].id = i;
	}
	sort(ls+1, ls+n*2+1, cmp);
	int cnt = 0;
	for (int i = 1; i <= n*2; i++)
	{
		vis[ls[i].id]++;
		if (ls[i].num - ls[i-1].num == 1)
			cnt++;
		if (ls[i].num - ls[i-1].num > 1)
			cnt+=2;
		if (vis[ls[i].id] == 1)
			d[ls[i].id].l = cnt;
		else
			d[ls[i].id].r = cnt, d[ls[i].id].len = d[ls[i].id].r - d[ls[i].id].l + 1;
	}
	sort(d+1, d+n+1, cmmp);
	int ans = 1;
	for (int i = 1; i <= n; i++)
	{
		int j = d[i].l;
		bool flag = 0;
		while (j <= d[i].r)
		{
			if (!used[j].vi)
			{
				flag = 1;
				used[j].vi = 1;
				used[j].l = d[i].l;
				used[j].r = d[i].r;
			}
			else
			{
				if (used[j].r == d[i].r && !flag)
					ans+=2;
				j = used[j].r;
			}
			j++;
		}
		if (flag)
			ans++;
	}
	cout << ans;
	return 0;
}