早就 A 了，偶然看到我的一个 219892 KiB 的代码，于是写下题解 .
https://www.luogu.com.cn/problem/P5025，BZOJ 过了，luogu 没过
题解：
先线段树优化建图，跑 tarjan 缩点，跑的时候记录强连通分量能到达的左右端点，然后再 dfs 一遍，用 \(u\) 能到的所有节点 \(v\) 来更新它能到的左右端点 .
然后就能求权值和了，答案显然能求了 .
时间复杂度 \(O(n\log n)\) .
丑陋の代码：
#include<iostream>
#include<ctime>
#include<queue>
#include<stack>
#include<cmath>
#include<iterator>
#include<cctype>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=5e5+500,M=2e6+500,MOD=1e9+7; // M = O(nlogn)
// warning 这里 M 开的是线段树点数，所以除了 x,r 其他数组都要开 M 大小
const ll INF_ll = 0x3f3f3f3f3f3f3f3f;
const int INF_int = 0x3f3f3f3f;
struct SimpleGraph
{
vector<int> g[M];
inline void addedge(int u,int v){g[u].push_back(v);}
inline void addedge2(int u,int v){addedge(u,v); addedge(v,u);}
void print(int n) // debug
{
for (int i=1;i<=n;i++)
{
printf("%d: ", i);
for (int v : g[i]) printf("%d, ", v);
puts("");
}
}
vector<int>& operator [] (const int& idx){return g[idx];}
inline vector<int>& out_edges(int u){return g[u];}
}g1,g2;
// g1 初始连边
// g2 缩完点
int n;
ll x[N], r[N];
namespace Tools
{
template<typename ptr>
inline void Unique(ptr begin,ptr end){sort(begin,end); unique(begin,end);}
inline bool in_range(int L,int R,int l,int r){return (l<=L)&&(R<=r);} // [L, R] in [l, r]
// Segment Tree Node: a
struct Range{int l,r; Range(int L,int R){l=L; r=R;} Range() = default;}a[M];
}
using namespace Tools;
namespace Tarjan
{
int dfn[M],low[M],belong[M],S[M],_left[M],_right[M],scc,tot,top;
bool vis[M];
void _dfs(int u)
{
dfn[u] = low[u] = ++tot; vis[u] = true;
S[++top] = u;
for (int v : g1[u])
{
if (!dfn[v]){_dfs(v); low[u] = min(low[u], low[v]);}
else low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int tmp; ++scc;
do
{
tmp = S[top];
belong[tmp] = scc;
vis[tmp] = false;
_left[scc] = min(_left[scc] , a[tmp].l);
_right[scc] = max(_right[scc], a[tmp].r);
--top;
} while (u != tmp);
}
}
}
namespace Seg // Segment Tree
{
#define lc (u<<1)
#define rc (u<<1|1)
#define mid ((l+r)>>1)
int ndcnt; // Node.
int id[N]; // map: number -> node
namespace __detail__
{
void connect(int u, int v, int L, int R, int l, int r)
{
if (in_range(l, r, L, R))
{
if (u == v) return ; // self
g1.addedge(v,u); return ;
}
if (L <= mid) connect(lc, v, L, R, l, mid);
if (R > mid) connect(rc, v, L, R, mid+1, r);
}
void build(int u,int l,int r)
{
a[u] = Range(l, r); ndcnt = max(ndcnt, u);
if (l == r)
{
id[l] = u;
return ;
}
build(lc, l, mid); build(rc, mid+1, r);
g1.addedge(u, lc); g1.addedge(u, rc);
}
}
void connect(int v,int L,int R){__detail__::connect(1,v,L,R,1,n);}
void build(){__detail__::build(1,1,n);}
#undef lc
#undef rc
#undef mid
}
namespace ALL{using namespace Seg; using namespace Tarjan;}
ll query(int x)
{
using namespace ALL;
int u = belong[id[x]];
return _right[u] - _left[u] + 1;
}
void dfs(int u)
{
using namespace ALL;
vis[u] = true;
for (int v : g2[u])
{
if (!vis[v]) dfs(v);
_left[u] = min(_left[u] , _left[v]);
_right[u] = max(_right[u], _right[v]);
}
}
inline void _(){puts("APJ AK IOI!!");}
int main()
{
#ifndef ONLINE_JUDGE
freopen("i.in","r",stdin);
#endif
using namespace ALL;
memset(_left,INF_int,sizeof _left);
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lld%lld",x+i,r+i);
x[n+1] = INF_ll;
build();
for (int i=1;i<=n;i++)
{
if (!r[i]) continue;
int L = lower_bound(x+1, x+1+n, x[i]-r[i]) - x,
R = upper_bound(x+1, x+1+n, x[i]+r[i]) - x - 1;
connect(id[i], L, R);
a[id[i]]=Range(L, R);
}
_dfs(1);
for (int u=1;u<=ndcnt;u++)
for (int v : g1[u])
{
int U=belong[u], V=belong[v];
if (U!=V) g2.addedge(U, V);
}
for (int i=1;i<=scc;i++) Unique(g2[i].begin(), g2[i].end());
memset(vis,false,sizeof vis);
for(int i=1;i<=scc;i++)
if (!vis[i]) dfs(i);
ll ans=0;
for (int i=1;i<=n;i++) ans = (ans + query(i) * i) % MOD;
printf("%lld\n", ans);
return 0;
}