Bzoj5017 [snow2017] bomb (tarjan shrink point + topological order dp + line merging + line tree optimization)

First of all, we can find that the bombs that can be detonated at each point are in a continuous range. Adjacent points can detonate in a certain distance. Each point is connected to the point that he can detonate, and a directed graph is built. Tarjan shrinks the point (the points in a scc can reach each other, and the range that they can reach can be combined), and then the topological order is inverted dp. A transition is equivalent to a segment merge. Each point records the range that he can detonate finally, and the answer is the range size.
But we have O(n2) edge in the worst case, which is unacceptable both in time and space. Fortunately, every point that we can connect to is a continuous interval. We can use the line tree to optimize the mapping, and divide each interval into the points on the most logn line tree. So we have the number of sides and the number of points of O(nlogn). There should also be edges between nodes on the segment tree. So the number of sides is the worst nlogn+2n.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 500010
#define mod 1000000007
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int n,L1[N<<2],R1[N<<2],h[N<<2],num=0,tot=0,in[N<<2],q[N<<2],h1=0,t=0;
ll pos[N],rg[N],ans=0;
int dfn[N<<2],low[N<<2],dfnum=0,scc,bel[N<<2],L[N<<2],R[N<<2],id[N];
bool inq[N<<2];
struct edge{
    int fr,to,next;
}data[N*20];
inline void add(int x,int y){
    if(x==y) return;
    data[++num].to=y;data[num].next=h[x];h[x]=num;data[num].fr=x;
}
inline void build(int p,int l,int r){
    tot=max(tot,p);L1[p]=l;R1[p]=r;
    if(l==r){id[l]=p;return;}int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    add(p,p<<1);add(p,p<<1|1);
}
inline void ask(int p,int l,int r,int x,int y,int s){
    if(x<=l&&r<=y){add(s,p);return;}
    int mid=l+r>>1;
    if(x<=mid) ask(p<<1,l,mid,x,y,s);
    if(y>mid) ask(p<<1|1,mid+1,r,x,y,s);
}
stack<int>qq;
inline void tarjan(int x){
    dfn[x]=low[x]=++dfnum;qq.push(x);inq[x]=1;
    for(int i=h[x];i;i=data[i].next){
        int y=data[i].to;
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
        else if(inq[y]) low[x]=min(low[x],dfn[y]);
    }if(dfn[x]==low[x]){
        ++scc;L[scc]=inf;
        while(1){
            int y=qq.top();qq.pop();inq[y]=0;bel[y]=scc;
            L[scc]=min(L[scc],L1[y]);R[scc]=max(R[scc],R1[y]);
            if(y==x) break;
        }
    }
}
int main(){
//  freopen("a.in","r",stdin);
    n=read();for(int i=1;i<=n;++i) pos[i]=read(),rg[i]=read();
    build(1,1,n);
    for(int i=1;i<=n;++i){
        int l=lower_bound(pos+1,pos+n+1,pos[i]-rg[i])-pos;
        int r=upper_bound(pos+1,pos+n+1,pos[i]+rg[i])-pos-1;
        if(l==r) continue;ask(1,1,n,l,r,id[i]);
    }for(int i=1;i<=tot;++i) if(!dfn[i]) tarjan(i);memset(h,0,sizeof(h));
    for(int i=1;i<=num;++i){
        int x=data[i].fr,y=data[i].to;
        if(bel[x]==bel[y]) continue;in[bel[y]]++;
        data[i].fr=bel[x];data[i].to=bel[y];data[i].next=h[bel[x]];h[bel[x]]=i;
    }for(int i=1;i<=scc;++i) if(!in[i]) q[++t]=i;
    while(h1<t){
        int x=q[++h1];
        for(int i=h[x];i;i=data[i].next){
            int y=data[i].to;if(--in[y]==0) q[++t]=y;
        }
    }for(int ii=scc;ii>=1;--ii){
        int x=q[ii];
        for(int i=h[x];i;i=data[i].next){
            int y=data[i].to;L[x]=min(L[x],L[y]);R[x]=max(R[x],R[y]);
        }
    }for(int i=1;i<=n;++i) ans=(ans+(ll)i*(R[bel[id[i]]]-L[bel[id[i]]]+1))%mod;
    printf("%lld\n",ans);
    return 0;
}

Posted on Sat, 02 May 2020 03:03:25 -0700 by saltedm8