bzoj 5017: [Snoi2017]炸彈 線段樹優化建圖+tarjan+拓撲排序

題意

在一條直線上有 N 個炸彈，每個炸彈的坐标是 Xi，爆炸半徑是 Ri，當一個炸彈爆炸時，如果另一個炸彈所在位置 Xj 滿足： Xi−Ri≤Xj≤Xi+Ri,那麼，該炸彈也會被引爆。

現在，請你幫忙計算一下，先把第 i 個炸彈引爆，将引爆多少個炸彈呢？

N≤500000

−10^18≤Xi≤10^18

0≤Ri≤2×10^18

分析

大概就是說，每個炸彈可以向一段連續的區間連邊，要求每個炸彈能到達的編号最小和最大的點。

因為是區間，顯然可以用線段樹優化建圖。然後就是tarjan+拓撲排序的套路了。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define MAX(x,y) x=max(x,y)
#define MIN(x,y) x=min(x,y)
using namespace std;

typedef long long LL;

const int N=500005;
const int MOD=1000000007;
const int inf=1000000000;

int n,sz,cnt,last[N*5],num[N*4],dfn[N*5],low[N*5],tim,deg[N*5],tot,mn[N*5],mx[N*5],a[N*5],stack[N*5],top,bel[N*5];
LL p[N],r[N];
bool ins[N*5];
struct edge{int to,next,from;}e[N*50];

void addedge(int u,int v)
{
    e[++cnt].from=u;e[cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}

void build(int d,int l,int r)
{
    num[d]=++sz;
    if (l==r) {addedge(num[d],l);return;}
    int mid=(l+r)/2;
    build(d*2,l,mid);build(d*2+1,mid+1,r);
    addedge(num[d],num[d*2]);addedge(num[d],num[d*2+1]);
}

void work(int d,int l,int r,int x,int y,int id)
{
    if (l==x&&r==y) {addedge(id,num[d]);return;}
    int mid=(l+r)/2;
    if (y<=mid) work(d*2,l,mid,x,y,id);
    else if (x>mid) work(d*2+1,mid+1,r,x,y,id);
    else work(d*2,l,mid,x,mid,id),work(d*2+1,mid+1,r,mid+1,y,id);
}

void tarjan(int x)
{
    dfn[x]=low[x]=++tim;
    stack[++top]=x;ins[x]=1;
    for (int i=last[x];i;i=e[i].next)
        if (!dfn[e[i].to]) tarjan(e[i].to),low[x]=min(low[x],low[e[i].to]);
        else if (ins[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    if (dfn[x]==low[x])
    {
        tot++;mn[tot]=inf;mx[tot]=0;int y=0;
        while (y!=x)
        {
            y=stack[top];top--;
            ins[y]=0;bel[y]=tot;
            if (y<=n) MIN(mn[tot],y),MAX(mx[tot],y);
        }
    }
}

void solve()
{
    int a1=0;
    for (int i=1;i<=tot;i++) if (!deg[i]) a[++a1]=i;
    for (int i=1;i<=a1;i++)
        for (int j=last[a[i]];j;j=e[j].next)
        {
            deg[e[j].to]--;
            if (!deg[e[j].to]) a[++a1]=e[j].to;
        }
    for (int i=tot;i>=1;i--)
    {
        int x=a[i];
        for (int j=last[x];j;j=e[j].next) MIN(mn[x],mn[e[j].to]),MAX(mx[x],mx[e[j].to]);
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld%lld",&p[i],&r[i]);
    sz=n;build(1,1,n);
    for (int i=1;i<=n;i++)
    {
        int x=lower_bound(p+1,p+n+1,p[i]-r[i])-p;
        int y=upper_bound(p+1,p+n+1,p[i]+r[i])-p-1;
        work(1,1,n,x,y,i);
    }
    for (int i=1;i<=sz;i++) if (!dfn[i]) tarjan(i);
    memset(last,0,sizeof(last));
    int tmp=cnt;
    for (int i=1;i<=tmp;i++)
        if (bel[e[i].from]!=bel[e[i].to])
        {
            addedge(bel[e[i].from],bel[e[i].to]);
            deg[bel[e[i].to]]++;
        }
    solve();
    int ans=0;
    for (int i=1;i<=n;i++) ans+=(LL)i*(mx[bel[i]]-mn[bel[i]]+1)%MOD,ans-=ans>=MOD?MOD:0;
    printf("%d",ans);
    return 0;
}