D. 实验室传染病
题意
给出 n 个人的位置，以及每个人的传染范围，当一个人患病时，他的传染范围内（包括边界上）的人全部会被感染并继续向外传播。
求以每个人为传染源最多有多少人被感染。
分析
首先二分预处理每个人一次最远感染到的人，然后线段树维护区间，表示每个点最远感染到右边的人以及感染到左边的人，不断查询，并扩大区间，因为右边最远点可能由于左边的传染点导致的。
最后，更新的时候要随机一个1~n的序列，不然会超时，应该有一组数据会卡掉按顺序更新的。
3
1 2
4 2
7 1
ans: 1 1 1
7
-21 19
-2 2
8 8
18 10
20 1
22 1
0 20
ans:7 6 6 6 1 1 6
5
0 20
8 3
10 1
18 10
20 1
ans: 5 2 1 4 1
code
#include<cstdio>
#include<algorithm>
#include<cstring>
#define rson m + 1, r, rt << 1 | 1
#define lson l, m, rt << 1
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int MAXN = 1e5 + 10;
const int INF = 2e9;
struct node
{
int x, d, id;
bool operator < (const node& other) const
{
return x < other.x;
}
}a[MAXN];
int r_[MAXN], l_[MAXN];
int ans[MAXN];
int n;
int mnl[MAXN << 2], mxr[MAXN << 2];
void PushUp(int rt)
{
mnl[rt] = min(mnl[rt << 1], mnl[rt << 1 | 1]);
mxr[rt] = max(mxr[rt << 1], mxr[rt << 1 | 1]);
}
void build(int l, int r, int rt)
{
if(l == r)
{
mnl[rt] = l_[l];
mxr[rt] = r_[l];
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUp(rt);
}
void update(int pos, int l0, int r0, int l, int r, int rt)
{
if(l == r)
{
mxr[rt] = max(mxr[rt], r0);
mnl[rt] = min(mnl[rt], l0);
return;
}
int m = (l + r) >> 1;
if(m >= pos) update(pos, l0, r0, lson);
else update(pos, l0, r0, rson);
PushUp(rt);
}
P query(int L, int R, int l, int r, int rt)
{
if(L <= l && R >= r)
{
return P(mnl[rt], mxr[rt]);
}
int m = (l + r) >> 1;
P p(INF, 0);
if(m >= L)
{
p = query(L, R, lson);
}
if(m < R)
{
P tmp = query(L, R, rson);
p.first = min(p.first, tmp.first);
p.second = max(p.second, tmp.second);
}
return p;
}
void init() // 找一次感染最远感染点
{
for(int i = 1; i <= n; i++)
{
r_[i] = upper_bound(a + 1, a + 1 + n, node{a[i].x + a[i].d, 0, 0}) - a - 1;
l_[i] = lower_bound(a + 1, a + 1 + n, node{a[i].x - a[i].d, 0, 0}) - a;
}
}
vector<int> v;
int main()
{
while(~scanf("%d", &n))
{
v.clear();
for(int i = 0; i < MAXN * 4; i++)
{
mnl[i] = INF;
mxr[i] = 0;
}
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].x, &a[i].d);
a[i].id = i;
v.push_back(i);
}
sort(a + 1, a + 1 + n);
init();
build(1, n, 1);
random_shuffle(v.begin(), v.end());
for(int j = 0; j < n; j++)
{
int i = v[j];
int l0 = l_[i], r0 = r_[i];
while(true)
{
P p = query(l0, r0, 1, n, 1);
if(p.first == l0 && p.second == r0) break;
l0 = p.first;
r0 = p.second;
}
update(i, l0, r0, 1, n, 1);
ans[a[i].id] = r0 - l0 + 1;
}
for(int i = 1; i <= n; i++)
{
printf("%d%c", ans[i], i == n ? '\n' : ' ');
}
}
return 0;
}