线段树优化建图，然后跑一边tarjan把点全部缩起来，炸一次肯定是有连锁反应的所以整个连通块都一样…于是就可以发现有些是只有单向边的不能忘记更新,没了。
#include <bits/stdc++.h>
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep(i , j , k) for(int i = j ; i <= k ; i ++)
#define Rep(i , j , k) for(int i = j ; i >= k ; i --)
using namespace std ;
using ll = long long ;
using pii = pair <int , int> ;
using vii = vector <int> ;
#define int long long
auto ot = [&]() { cerr << "ATS TXDY" << '
' ; int ATS_nantf_txdy = true ; } ;
auto _ios = [&]() { ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ; } ;
namespace stO_ATS_Orz {
template < class T > void cmax(T & x , T y) { if(x < y) x = y ; }
template < class T > void cmin(T & x , T y) { if(x > y) x = y ; }
template < class T > void abs(T x) { if(x < 0) x = -x ; }
const int N = 5e5 + 10 ;
const int mod = 1e9 + 7 ;
int n , a[N] , r[N] , id[N] ;
int minl[N << 2] , maxr[N << 2] , sccl[N << 2] , sccr[N << 2] , mx = 0 ;
vii G[N << 2] ;
void build(int l , int r , int p) {
minl[p] = l ; maxr[p] = r ; cmax(mx , p) ;
if(l == r) { id[l] = p ; return ; }
int mid = l + r >> 1 ;
build(l , mid , p << 1) ; build(mid + 1 , r , p << 1 | 1) ;
G[p].push_back(p << 1) ; G[p].push_back(p << 1 | 1) ;
}
void upd(int a , int b , int l , int r , int p , int to) {
if(a <= l && r <= b) { if(p ^ to) G[to].push_back(p) ; return ; }
int mid = l + r >> 1 ;
if(a <= mid) upd(a , b , l , mid , p << 1 , to) ;
if(b > mid) upd(a , b , mid + 1 , r , p << 1 | 1 , to) ;
}
int low[N << 2] , dfn[N << 2] , idx = 0 ;
int col[N << 2] , st[N << 2] , tp = 0 , num = 0 ;
void tarjan(int u) {
low[u] = dfn[u] = ++ idx ; st[++ tp] = u ;
for(int v : G[u]) {
if(! dfn[v]) { tarjan(v) ; cmin(low[u] , low[v]) ; }
else if(! col[v]) { cmin(low[u] , dfn[v]) ; }
}
if(low[u] == dfn[u]) {
++ num ;
do { col[st[tp]] = num ; cmin(sccl[num] , minl[st[tp]]) ; cmax(sccr[num] , maxr[st[tp]]) ; tp -- ; } while(st[tp + 1] ^ u) ;
}
}
vii reG[N << 2] ;
bool vis[N << 2] ;
void dfs(int u) {
vis[u] = 1 ;
for(int v : reG[u]) {
if(vis[v]) { cmin(sccl[u] , sccl[v]) ; cmax(sccr[u] , sccr[v]) ; }
else { dfs(v) ; cmin(sccl[u] , sccl[v]) ; cmax(sccr[u] , sccr[v]) ; }
}
}
void main() {
cin >> n ; build(1 , n , 1) ;
for(int i = 1 ; i <= n ; i ++) { cin >> a[i] >> r[i] ; }
a[n + 1] = 1e18 ; memset(sccl , 0x3f , sizeof(sccl)) ;
for(int i = 1 ; i <= n ; i ++) {
if(! r[i]) { continue ; }
int bg = lower_bound(a + 1 , a + n + 1 , a[i] - r[i]) - a ;
int ed = upper_bound(a + 1 , a + n + 1 , a[i] + r[i]) - a - 1 ;
upd(bg , ed , 1 , n , 1 , id[i]) ; minl[id[i]] = bg ; maxr[id[i]] = ed ;
}
rep(i , 1 , mx) if(! dfn[i]) tarjan(i) ;
rep(i , 1 , mx)
for(int v : G[i])
if(col[i] ^ col[v]) reG[col[i]].push_back(col[v]) ;
memset(vis , 0 , sizeof(vis)) ;
rep(i , 1 , num) if(! vis[i]) dfs(i) ;
int ans = 0 ;
rep(i , 1 , n) ans = (ans + i * (sccr[col[id[i]]] - sccl[col[id[i]]] + 1)) % mod ;
cout << ans << '
' ;
}
}
signed main() {
_ios() ; ot() ;
return stO_ATS_Orz :: main() , 0 ;
}