题解 P5025 【[SNOI2017]炸弹】
whyl
2019-08-28 21:15:58
蒟蒻第一次AC黑题，来写一篇题解来纪念一下
就是线段树优化建图
1.把每个叶子节点（就是真正的炸弹）在线段树上可以炸到范围的区间（和普通线段树一样）连一条边。
2.tarjan缩点，每个强联通分量的权值记为当前强联通分量包含的炸弹数。
3.连边，注意边要见反向（为了topsort），并且不能有重边。
4.topsort，将自己的权值传给自己的后继
5.输出答案。
时间复杂度nlogn，空间复杂度nlogn。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mid ((l+r)>>1)
#define lson k<<1,l,mid
#define rson k<<1|1,mid+1,r
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+p-48,p=getchar();
return x*f;
}
long long ans;
const int maxn=5e5+5,mod=1e9+7;
int s[maxn<<2],low[maxn<<2],dfn[maxn<<2],n,b[maxn],a[maxn],tot;
int x[maxn],tree[maxn<<2],headedge[maxn<<2],veredge[maxn<<2];
int head[maxn<<2],nxt[maxn*25],ver[maxn*25],scc,col[maxn<<2];
int v[maxn<<2],id[maxn],cnt,top,nxtedge[maxn<<2],cntedge;
int w[maxn<<2],nod,rd[maxn<<2],f[maxn<<2];
map<pair<int,int>,int> Map;
inline void add(int x,int y){
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
}
inline void addedge(int x,int y){
nxtedge[++cntedge]=headedge[x];
headedge[x]=cntedge;
veredge[cntedge]=y;
}
inline void build(int k,int l,int r){
if(l==r){
nod=max(nod,k);
id[l]=k;
return;
}
build(lson);
build(rson);
add(k,k<<1);
add(k,k<<1|1);
}
inline void connect(int k,int l,int r,int L,int R,int pos){
if(L<=l&&r<=R){
if(id[pos]==k) return;
add(id[pos],k);
return;
}
if(L<=mid) connect(lson,L,R,pos);
if(R>mid) connect(rson,L,R,pos);
return;
}
inline void tarjan(int x){
dfn[x]=low[x]=++tot;
s[++top]=x;
v[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(v[y]) low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int tmp;
scc++;
do{
tmp=s[top--];
col[tmp]=scc;
v[tmp]=0;
}while(x!=tmp);
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++) b[i]=a[i]=read(),x[i]=read();
//线段树
build(1,1,n);
for(int i=1;i<=n;i++){
int l=lower_bound(b+1,b+1+n,a[i]-x[i])-b;
int r=(upper_bound(b+1,b+1+n,a[i]+x[i])-b)-1;
connect(1,1,n,l,r,i);
}
//tarjan
for(int i=1;i<=nod;i++) if(!dfn[i]) tarjan(i);
for(int i=1;i<=n;i++) w[col[id[i]]]++;
//连边
for(int x=1;x<=nod;x++){
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(col[x]==col[y]) continue;
pair<int,int> t;
t.first=col[y],t.second=col[x];
if(Map[t]==1) continue;
addedge(col[y],col[x]);
Map[t]=1;
++rd[col[x]];
}
}
//topsort
queue<int> q;
for(int i=1;i<=scc;i++) if(rd[i]==0) q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
f[x]+=w[x];
for(int i=headedge[x];i;i=nxtedge[i]){
int y=veredge[i];
f[y]+=f[x];
rd[y]--;
if(rd[y]==0) q.push(y);
}
}
//统计答案
for(int i=1;i<=n;i++) ans=(ans+i*f[col[id[i]]]%mod)%mod;
cout<<ans<<endl;
return 0;
}
```
6.等待AC。
蒟蒻第一次写黑题题解，求管理放过，谢谢。