题解 P5025 【[SNOI2017]炸弹】

暴力： 对于每一个炸弹，枚举所有的炸弹，看它爆炸能不能引爆那个炸弹 如果能，由这个炸弹向引爆的炸弹连单向边 tarjan所点后拓扑排序 在拓扑图上倒着统计答案 可以得到一个炸弹能引爆的编号最小mi和最大的炸弹mx，mx-mi+1就是先引爆这个炸弹一共能引爆的炸弹数 优化： 一个炸弹一定是向一段区间连边 所以用线段树优化，这样向一个区间连边就变成了向一个点连边 注意存边的空间一定要开的足够大 还有tarjan缩完点后不一定是一棵树，因为是有向图缩点 CODE： ``` #include<cstdio> #include<vector> #include<iostream> #include<algorithm> using namespace std; const int mod=1e9+7; #define N 500001 typedef long long LL; int n; int id[N*3],num; int front[N*3],to[N*21],nxt[N*21],from[N*21],tot; LL pos[N],rad[N]; int dfn[N*3],low[N*3],tim; int st[N*3],top; bool vis[N*3]; int cnt; int bl[N*3],mi[N*3],mx[N*3]; vector<int>V[N*3]; int in[N*3]; int q[N*3]; template<typename T> void read(T &x) { x=0; int f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } x*=f; } void add(int u,int v) { to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; //printf("%d %d\n",u,v); } /*void add2(int u,int v) { to2[++tot2]=v; nxt2[tot2]=front2[u]; front2[u]=tot2; }*/ void build(int k,int l,int r) { id[k]=++num; if(l==r) { add(id[k],l); return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); add(id[k],id[k<<1]); add(id[k],id[k<<1|1]); } void burst(int k,int l,int r,int opl,int opr,int who) { if(l>=opl && r<=opr) { add(who,id[k]); return; } int mid=l+r>>1; if(opl<=mid) burst(k<<1,l,mid,opl,opr,who); if(opr>mid) burst(k<<1|1,mid+1,r,opl,opr,who); } void init() { read(n); num=n; build(1,1,n); for(int i=1;i<=n;++i) read(pos[i]),read(rad[i]); for(int i=1;i<=n;++i) burst(1,1,n,lower_bound(pos+1,pos+n+1,pos[i]-rad[i])-pos,upper_bound(pos+1,pos+n+1,pos[i]+rad[i])-pos-1,i); } void tarjan(int x) { dfn[x]=low[x]=++tim; st[++top]=x; vis[x]=true; for(int i=front[x];i;i=nxt[i]) if(!dfn[to[i]]) { tarjan(to[i]); low[x]=min(low[x],low[to[i]]); } else if(vis[to[i]]) low[x]=min(low[x],dfn[to[i]]); int y; if(low[x]==dfn[x]) { cnt++; mi[cnt]=n+1; mx[cnt]=0; while(x!=y) { y=st[top--]; vis[y]=false; bl[y]=cnt; if(y<=n) { mi[cnt]=min(mi[cnt],y); mx[cnt]=max(mx[cnt],y); } } } } void rebuild() { for(int i=1;i<=tot;++i) if(bl[from[i]]!=bl[to[i]]) { //add2(bl[from[i]],bl[to[i]]); V[bl[from[i]]].push_back(bl[to[i]]); in[bl[to[i]]]++; } } void topsort() { int head=1,tail=1; for(int i=1;i<=cnt;++i) if(!in[i]) q[tail++]=i; int now,siz,t; while(head<tail) { now=q[head++]; siz=V[now].size(); for(int i=0;i<siz;++i) { t=V[now][i]; in[t]--; if(!in[t]) q[tail++]=t; } } for(int i=tail-1;i;--i) { now=q[i]; siz=V[now].size(); for(int i=0;i<siz;++i) { t=V[now][i]; mi[now]=min(mi[now],mi[t]); mx[now]=max(mx[now],mx[t]); } } } void work() { // printf("%d %d\n",num,tot); for(int i=1;i<=num;++i) if(!dfn[i]) tarjan(i); rebuild(); topsort(); int ans=0; for(int i=1;i<=n;++i) { ans+=1LL*i*(mx[bl[i]]-mi[bl[i]]+1)%mod; ans-=ans>=mod ? mod : 0; } printf("%d",ans); } int main() { init(); work(); } ```