bzoj5017[Snoi2017]炸弹
luoguP5025
给定n个炸弹和它们的爆炸半径，在爆炸半径中的其它炸弹会被引爆，求每个炸弹爆炸后一共能引爆几个炸弹
从每个炸弹向它能引爆的炸弹连边
因为它能引爆的炸弹是一个区间，所以可以用线段树优化一下
然后缩点，同时记录每个强连通分量中，最小和最大点的编号
最后dfs一遍用每条边的终点答案更新起点答案，也就是每个炸弹能炸掉的最左/右边的炸弹的编号，输出的时候用r[scc[i]]-l[scc[i]]+1就行了
最后输出的时候要开long long，不然就乘爆了
因为这个调了很久， 最后还是@北辰yama大佬帮我指出了错误，感谢%%%
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<queue>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline LL read(){
LL x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
struct datae{
int from,to;
}e[10000006];
int n,nn;
LL x[500006],banjing[500006];
int in[2000006];
int fir[2000006],nex[20000006],to[20000006],etot;
struct tr{
tr *ls,*rs;
int id;
}dizhi[1000006],*root=&dizhi[0];
int tot;
int idtol[20000006],idtor[20000006];
int low[2000006],dfn[2000006],dfscnt;
int scc[2000006],sccminid[2000006],sccmaxid[2000006],scccnt;
int vis[2000006];
int stack[2000006],top;
inline void updatamin(int &xx,int xxx){(xx>xxx)&&(xx=xxx);}
inline void updatamax(int &xx,int xxx){(xx<xxx)&&(xx=xxx);}
inline void add(int u,int v,int tmp){
to[++etot]=v;
if(tmp) e[etot].from=u,e[etot].to=v;
nex[etot]=fir[u];fir[u]=etot;
}
void build(tr *tree,int l,int r){
if(l==r) return tree->id=idtol[l]=idtor[l]=l,void();
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
tree->id=++nn;
idtol[nn]=l;idtor[nn]=r;
add(tree->id,tree->ls->id,1);add(tree->id,tree->rs->id,1);
}
void addtree(tr *tree,int l,int r,int ql,int qr,int u){
if(ql<=l&&r<=qr){
if(tree->id!=u) add(u,tree->id,1);
return;
}
int mid=(l+r)>>1;
if(ql<=mid) addtree(tree->ls,l,mid,ql,qr,u);
if(qr>mid) addtree(tree->rs,mid+1,r,ql,qr,u);
}
inline int dayu(LL xx){
R int l=1,r=n,mid,ret;
while(l<=r){
mid=(l+r)>>1;
if(x[mid]>=xx) ret=mid,r=mid-1;
else l=mid+1;
}
return ret;
}
inline int xiaoyu(LL xx){
R int l=1,r=n,mid,ret;
while(l<=r){
mid=(l+r)>>1;
if(x[mid]<=xx) ret=mid,l=mid+1;
else r=mid-1;
}
return ret;
}
void tarjan(R int u){
dfn[u]=low[u]=++dfscnt;
stack[top++]=u;
for(R int i=fir[u];i;i=nex[i]){
R int v=to[i];
if(!dfn[v]){
tarjan(v);
updatamin(low[u],low[v]);
}
else if(!scc[v]) updatamin(low[u],low[v]);
}
if(dfn[u]==low[u]){
scccnt++;
sccminid[scccnt]=1e9;
do{
top--;
updatamin(sccminid[scccnt],idtol[stack[top]]);
updatamax(sccmaxid[scccnt],idtor[stack[top]]);
scc[stack[top]]=scccnt;
}while(stack[top]!=u);
}
}
void dfs(R int u){
vis[u]=1;
for(R int i=fir[u];i;i=nex[i]){
R int v=to[i];
if(vis[v]){
updatamin(sccminid[u],sccminid[v]);
updatamax(sccmaxid[u],sccmaxid[v]);
}
else{
dfs(v);
updatamin(sccminid[u],sccminid[v]);
updatamax(sccmaxid[u],sccmaxid[v]);
}
}
}
int main(){
nn=n=read();
LL minx=2e18,maxx=-2e18;
for(R int i=1;i<=n;i++){
x[i]=read();banjing[i]=read();
minx=std::min(minx,x[i]);maxx=std::max(maxx,x[i]);
}
build(root,1,n);
for(R int i=1;i<=n;i++){
if(!banjing[i]) continue;
int lll=dayu(std::max(x[i]-banjing[i],minx)),rrr=xiaoyu(std::min(maxx,x[i]+banjing[i]));
addtree(root,1,n,lll,rrr,i);
}
for(R int i=1;i<=nn;i++)
if(!dfn[i]) tarjan(i);
std::memset(fir,0,sizeof fir);std::memset(nex,0,sizeof nex);
std::memset(to,0,sizeof to);
tot=etot;etot=0;
for(R int i=1;i<=tot;i++)if(scc[e[i].from]!=scc[e[i].to])
add(scc[e[i].from],scc[e[i].to],0),in[scc[e[i].to]]++;
for(R int i=1;i<=scccnt;i++)
if(!vis[i]) dfs(i);
R LL ans=0,mod=1e9+7;
for(R int i=1;i<=n;i++)
ans+=(1ll*(sccmaxid[scc[i]]-sccminid[scc[i]]+1)*i)%mod,
ans%=mod;
std::printf("%lld",ans);
return 0;
}