RT,已经跟题解进行了 肉眼对拍和 对拍,没找出问题,第一、二个点WA,已经处理了 x 不是升序的问题。
#include <bits/stdc++.h>
#define ll long long
const ll WY=1e9+7;
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}
template<typename T>void print(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) print(x/10);
putchar(x%10+'0');
}
const ll MAXN=6e5+5;
ll x[MAXN<<2],rr[MAXN<<2],id[MAXN<<2];
ll NodeNum;
struct Interval{
ll l,r;
Interval(){l=0,r=0;}
Interval(ll L,ll R){l=L,r=R;}
}P[MAXN<<2];
map <ll,bool> M[MAXN<<2];
vector <ll> G[MAXN<<2],G_[MAXN<<2];
ll L[MAXN<<2],R[MAXN<<2];
struct SegmentTree{
#define ls p<<1
#define rs p<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
void build(ll p,ll l,ll r)
{
P[p]=Interval(l,r);
NodeNum=max(NodeNum,p);
if(l==r)
{
id[l]=p;
return;
}
ll mid=(l+r)>>1;
build(lson);build(rson);
G[p].push_back(ls);
G[p].push_back(rs);
}
void Add(ll p,ll l,ll r,ll lx,ll rx,ll From)
{
if(lx<=l&&r<=rx)
{
if(p==From) return;
G[From].push_back(p);
return;
}
ll mid=(l+r)>>1;
if(lx<=mid) Add(lson,lx,rx,From);
if(rx>mid) Add(rson,lx,rx,From);
}
}tr;
stack<ll> S;
bool InStack[MAXN<<2];
ll dfn[MAXN<<2],low[MAXN<<2],Times,tot;
ll belong[MAXN<<2];
void Tarjan(ll u)
{
dfn[u]=low[u]=++Times;
S.push(u);
InStack[u]=true;
for(ll i=0;i<(ll)G[u].size();i++)
{
ll v=G[u][i];
if(!dfn[v])
{
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(InStack[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
ll t=-1;
tot++;
while(t!=u)
{
t=S.top();
S.pop();
InStack[u]=false;
belong[t]=tot;
L[tot]=min(L[tot],P[t].l);
R[tot]=max(R[tot],P[t].r);
}
}
}
bool vis[MAXN<<2];
void dfs(int u){ //最后一遍 dfs 更新
vis[u] = true;
int v,l = G_[u].size();
for(int i=0;i!=l;++i){
v = G_[u][i];
if(vis[v]){
L[u] = min(L[u],L[v]);
R[u] = max(R[u],R[v]);
continue;
}
dfs(v);
L[u] = min(L[u],L[v]);
R[u] = max(R[u],R[v]);
}
}
struct node{
ll x,r;
}Op[MAXN<<2];
inline bool cmp(node X,node Y)
{
return X.x<Y.x;
}
int main() {
// freopen("Bomb1.in","r",stdin);
// freopen("Bomb1.out","w",stdout);
memset(L,0x3f,sizeof(L));
ll n;
read(n);
for(ll i=1;i<=n;i++)
{
read(Op[i].x);
read(Op[i].r);
}
Op[n+1].x=0x3f3f3f3f3f3f3f3fll;
sort(Op+1,Op+2+n,cmp);
for(int i=1;i<=n+1;i++) x[i]=Op[i].x;
tr.build(1,1,n);
for(ll i=1,LL,RR;i<=n;i++)
{
if(!Op[i].r) continue;
LL=lower_bound(x+1,x+1+n,x[i]-Op[i].r)-x;
RR=upper_bound(x+1,x+1+n,x[i]+Op[i].r)-x-1;
tr.Add(1,1,n,LL,RR,id[i]);
P[id[i]]=Interval(LL,RR);
}
Tarjan(1);
for(ll u=1;u<=NodeNum;u++)
{
for(ll i=0;i<(ll)G[u].size();i++)
{
ll v=G[u][i];
ll X=belong[u],y=belong[v];
if(X==y||M[X][y]) continue;
G_[X].push_back(y);
M[X][y]=true;
}
}
ll ans=0;
for(ll i=1;i<=tot;i++) if(!vis[i]) dfs(i);
for(ll i=1;i<=n;i++)
{
ll tmp=0;
ll X=belong[id[i]];
tmp=R[X]-L[X]+1;
ans=(ans+tmp*i%WY)%WY;
}
printf("%lld",ans);
return 0;
}