先用线段树计算出两边最远，用左边更新右边，同时用右边更新左边 loj上100，洛谷84 WA#1#2 求助

#include <bits/stdc++.h>
using namespace std; 
#define ll __int128
#define int long long
const int N=5e5+10,mod=1e9+7;
int n,m;
struct node
{
    int x,r;
    
    bool operator<(const node &W) const
    {
        if(x!=W.x) return x<W.x;
        return r<W.r;
    }
}w[N];

int pre[N],suf[N];
int prex[N],sufx[N];

struct tree
{
    int l,r,a;
}tr1[N<<4],tr2[N<<4];

ll read()
{
    ll res=0,f=1;
    char op=getchar();
    while(!isdigit(op)) {if(op=='-') f*=-1;op=getchar();}
    while(isdigit(op)) res=(res*10)+op-'0',op=getchar();
    return res*f;
}

void pushup1(int u)
{
    tr1[u].a=min(tr1[u<<1].a,tr1[u<<1|1].a);//最小的编号
}

void pushup2(int u)
{
    tr2[u].a=max(tr2[u<<1].a,tr2[u<<1|1].a);//最小的编号
}

void build1(int u,int l,int r)
{
    tr1[u].l=l,tr1[u].r=r;
    if(l==r) {
        tr1[u].a=n+1;
        return ;
    }
    int mid=l+r>>1;
    build1(u<<1,l,mid);
    build1(u<<1|1,mid+1,r);
}

void build2(int u,int l,int r)
{
    tr2[u].l=l,tr2[u].r=r;
    if(l==r) {
        tr2[u].a=0;
        return ;
    }
    int mid=l+r>>1;
    build2(u<<1,l,mid);
    build2(u<<1|1,mid+1,r);
}

void modify1(int u,int l,int r,int x)
{
    if(l==r&&l==x)
    {
        tr1[u].a=prex[x];//编号最小
        return ;
    }
    
    int mid=l+r>>1;
    if(x<=mid) modify1(u<<1,l,mid,x);
    else modify1(u<<1|1,mid+1,r,x);
    
    pushup1(u);
}

void modify2(int u,int l,int r,int x)
{
    if(l==r&&l==x)
    {
        tr2[u].a=sufx[x];//编号最大
        return ;
    }
    
    int mid=l+r>>1;
    if(x<=mid) modify2(u<<1,l,mid,x);
    else modify2(u<<1|1,mid+1,r,x);
    
    pushup2(u);
}

int get_low(ll e)
{
    int l=1,r=n,ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(w[mid].x>=e) r=mid-1,ans=mid;
        else l=mid+1;
    }
    return ans;
}

int get_high(ll e)
{
    int l=1,r=n,ans=-1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(w[mid].x<=e) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}

int query1(int u,int l,int r)
{
    if(tr1[u].l>=l&&tr1[u].r<=r)
    {
        // if(l==3&&r==3) cout<<u<<' '<<tr[u].a<<endl;
        return tr1[u].a;
    }
    
    int mid=tr1[u].l+tr1[u].r>>1;
    int res=n+1;
    if(l<=mid) res=min(res,query1(u<<1,l,r));
    if(r>mid) res=min(res,query1(u<<1|1,l,r));
    return res;
}

int query2(int u,int l,int r)
{
    if(tr2[u].l>=l&&tr2[u].r<=r)
    {
        return tr2[u].a;
    }
    
    int mid=tr2[u].l+tr2[u].r>>1;
    int res=0;
    if(l<=mid) res=max(res,query2(u<<1,l,r));
    if(r>mid) res=max(res,query2(u<<1|1,l,r));
    return res;
}

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        w[i].x=read(),w[i].r=read();
    }
    sort(w+1,w+1+n);
    
    build1(1,1,n);
    
    for(int i=1;i<=n;i++)
    {
        if(i==1)
        {
            pre[i]=0;
            prex[i]=1;
            modify1(1,1,n,i);
        }
        else {
            int p=get_low(w[i].x-w[i].r);
            if(p==i) {
                pre[i]=0;
                prex[i]=i;
                modify1(1,1,n,i);
            }else {
                prex[i]=query1(1,p,i-1);
                pre[i]=i-prex[i];
                modify1(1,1,n,i);
            }
        }
    }
    
    build2(1,1,n);
    
    for(int i=n;i>=1;i--)
    {
        if(i==n)
        {
            suf[i]=0;
            sufx[i]=n;
            modify2(1,1,n,i);
        }
        else {
            int p=get_high(w[i].x+w[i].r);
            if(p==i) {
                suf[i]=0;
                sufx[i]=i;
                modify2(1,1,n,i);
            }else {
                sufx[i]=query2(1,i+1,p);
                suf[i]=sufx[i]-i;
                modify2(1,1,n,i);
            }
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        // cout<<prex[i]<<' '<<sufx[i]<<endl;
        int x=query1(1,i+1,sufx[i]);//后面能到的最前面
        int y=query2(1,prex[i],i-1);//前面能到的最后面
        // cout<<x<<' '<<y<<' '<<i<<endl;
        while(x<prex[i]||y>sufx[i])
        {
            if(x<prex[i]) prex[i]=x;
            if(y>suf[i]) sufx[i]=y;
            
            x=min(query1(1,prex[i],i-1),query1(1,i+1,sufx[i]));
            y=max(query2(1,prex[i],i-1),query2(1,i+1,sufx[i]));
        }
        
        pre[i]=i-prex[i];
        suf[i]=sufx[i]-i;
    }
    
    int res=0;
    for(int i=1;i<=n;i++)
    {
        int num=pre[i]+suf[i]+1;
        res=(res+num*i)%mod;
        // cout<<pre[i]<<' '<<suf[i]<<endl;
    }
    
    cout<<res<<endl;
}