题意

给出 n 个人的位置，以及每个人的传染范围，当一个人患病时，他的传染范围内（包括边界上）的人全部会被感染并继续向外传播。

求以每个人为传染源最多有多少人被感染。

分析

首先二分预处理每个人一次最远感染到的人，然后线段树维护区间，表示每个点最远感染到右边的人以及感染到左边的人，不断查询，并扩大区间，因为右边最远点可能由于左边的传染点导致的。

最后，更新的时候要随机一个1~n的序列，不然会超时，应该有一组数据会卡掉按顺序更新的。

31 24 27 1ans: 1 1 17-21 19-2 28 818 1020 122 10 20ans:7 6 6 6 1 1 650 208 310 118 1020 1ans: 5 2 1 4 1

code

#include
    
     #include
     
      #include
      
       #define rson m + 1, r, rt << 1 | 1#define lson l, m, rt << 1using namespace std;typedef long long ll;typedef pair
       
         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
        
          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;}