炸弹

早就 A 了，偶然看到我的一个 219892 KiB 的代码，于是写下题解 .

https://www.luogu.com.cn/problem/P5025，BZOJ 过了，luogu 没过

题解：

先线段树优化建图，跑 tarjan 缩点，跑的时候记录强连通分量能到达的左右端点，然后再 dfs 一遍，用 \(u\) 能到的所有节点 \(v\) 来更新它能到的左右端点 .

然后就能求权值和了，答案显然能求了 .

时间复杂度 \(O(n\log n)\) .

丑陋の代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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& operator [] (const int& idx){return g[idx];}
    inline vector& out_edges(int u){return g[u];}
}g1,g2;
// g1 初始连边
// g2 缩完点

int n;
ll x[N], r[N];
namespace Tools
{
    template
    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;
}
题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签