loj#2255. 「SNOI2017」炸弹 线段树优化建图，拓扑，缩点

loj#2255. 「SNOI2017」炸弹 线段树优化建图，拓扑，缩点

链接

loj

思路

用交错关系建出图来，发现可以直接缩点，拓扑统计。

完了吗，不，瓶颈在于边数太多了，线段树优化建图。

细节

建新图要判重。

内存永远算不对

代码

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e6+7,mod=1e9+7;

ll read() {

    ll x=0,f=1;char s=getchar();

    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

    return x*f;

}

int n,cnt,id[N<<2],ru[N<<2],ans[N<<2];

ll X[500007],R[500007];

int low[N<<2],dfn[N<<2],stak[N<<2],top,vis[N<<2],belong[N<<2],col,siz[N<<2],mmp;

vector<int> G[N<<2];

queue<int> q;

struct node {int v,nxt;}e[N<<4];

int head[N<<2],tot;

void add(int u,int v) {

    e[++tot].v=v;

    e[tot].nxt=head[u];

    head[u]=tot;

}

namespace seg {

    #define ls rt<<1

    #define rs rt<<1|1

    void build(int l,int r,int rt) {

        if(l==r) return id[rt]=l,void();

        int mid=(l+r)>>1;

        id[rt]=++cnt;

        build(l,mid,ls);

        build(mid+1,r,rs);

        add(id[rt],id[ls]);

        add(id[rt],id[rs]);

    }

    void update(int u,int L,int R,int l,int r,int rt) {

        if(L<=l&&r<=R) return add(u,id[rt]),void();

        int mid=(l+r)>>1;

        if(L<=mid) update(u,L,R,l,mid,ls);

        if(R>mid) update(u,L,R,mid+1,r,rs);

    }

}

void tarjan(int u) {

    dfn[u]=low[u]=++mmp;

    vis[u]=1;

    stak[++top]=u;

    for(int i=head[u];i;i=e[i].nxt) {

        int v=e[i].v;

        if(!dfn[v]) {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        } else if(vis[v]) {

            low[u]=min(low[u],dfn[v]);

        }

    }

    if(low[u]==dfn[u]) {

        ++col;

        while(stak[top]!=u) {

            belong[stak[top]]=col;

            vis[stak[top]]=0;

            if(stak[top]<=n) siz[col]++;

            top--;

        }

        belong[stak[top]]=col;

        vis[stak[top]]=0;

        if(stak[top]<=n) siz[col]++;

        top--;

    }

}

map<pair<int,int> ,int> Hash;

int main() {

    n=cnt=read();

    seg::build(1,n,1);

    for(int i=1;i<=n;++i) X[i]=read()+(ll)3e18,R[i]=read();

    for(int i=1;i<=n;++i) {

        int j=upper_bound(X+i,X+1+n,X[i]+R[i])-X-1;

        if(j!=i) seg::update(i,i+1,j,1,n,1);

        j=lower_bound(X+1,X+i,X[i]-R[i])-X;

        if(j!=i) seg::update(i,j,i-1,1,n,1);

    }

    for(int i=1;i<=cnt;++i)

        if(!dfn[i])

            tarjan(i);

    for(int u=1;u<=cnt;++u) {

        for(int i=head[u];i;i=e[i].nxt) {

            int v=e[i].v;

            if(belong[v]!=belong[u]&&!Hash[make_pair(belong[v],belong[u])]) {

                Hash[make_pair(belong[v],belong[u])]=1;

                G[belong[v]].push_back(belong[u]);

                ru[belong[u]]++;

            }

        }

    }

    for(int i=1;i<=col;++i) {

        if(!ru[i]) {

            q.push(i);

            siz[i]=siz[i];

        }

    }

    while(!q.empty()) {

        int u=q.front();

        q.pop();

        for(auto v:G[u]) {

            siz[v]+=siz[u];

            ru[v]--;

            if(!ru[v]) q.push(v);

        }

    }

    int ans=0;

    for(int i=1;i<=n;++i) {

        ans+=1LL*i*siz[belong[i]]%mod;

        ans%=mod;

    }

    printf("%d\n",ans);

}