bzoj5017 炸弹 (线段树优化建图+tarjan+拓扑序dp)

直接建图边数太多,用线段树优化一下

然后缩点,记下来每个点里有多少个炸弹

然后按拓扑序反向dp一下就行了

 #include<bits/stdc++.h>
#define pa pair<ll,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=5e5+,maxp=maxn*,maxl=maxn*,P=1e9+;
const ll inf=1e18+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N;
ll pos[maxn],r[maxn];
int rg[maxn][],id[maxn],ch[maxp][],pct,root;
int eg[maxl][],egh[maxp],ect;
int eg2[maxl][],egh2[maxp],ect2,ine[maxp];
int dfn[maxp],low[maxp],tot,stk[maxp],sh;
int bel[maxp],nct,hav[maxp],hh[maxp];
int val[maxp],rk[maxp];
bool instk[maxp],islef[maxp],to[maxp];
queue<int> q; inline void adeg(int a,int b){
eg[++ect][]=b;eg[ect][]=egh[a];egh[a]=ect;
}
inline void adeg2(int a,int b){
ine[b]++;
eg2[++ect2][]=b;eg2[ect2][]=egh2[a];egh2[a]=ect2;
} void build(int &p,int l,int r){
p=++pct;
if(l==r) id[l]=p,islef[p]=;
if(l<r){
int m=l+r>>;
build(ch[p][],l,m);
build(ch[p][],m+,r);
adeg(p,ch[p][]),adeg(p,ch[p][]);
}
} void conn(int p,int l,int r,int x,int y,int z){
if(x>y) return;
if(x<=l&&r<=y){
adeg(z,p);
}else{
int m=l+r>>;
if(x<=m) conn(ch[p][],l,m,x,y,z);
if(y>=m+) conn(ch[p][],m+,r,x,y,z);
}
} void tarjan(int x){
dfn[x]=low[x]=++tot;
stk[++sh]=x;instk[x]=;
for(int i=egh[x];i;i=eg[i][]){
int b=eg[i][];
if(instk[b]) low[x]=min(low[x],dfn[b]);
else if(!dfn[b]){
tarjan(b);
low[x]=min(low[x],low[b]);
}
}
if(dfn[x]==low[x]){
++nct;
while(sh){
bel[stk[sh]]=nct;
hav[stk[sh]]=hh[nct],hh[nct]=stk[sh];
val[nct]+=islef[stk[sh]];
instk[stk[sh]]=;
sh--;
if(stk[sh+]==x) break;
}
}
} int main(){
//freopen(".in","r",stdin);
int i,j,k;
N=rd();
for(i=;i<=N;i++) pos[i]=rd(),r[i]=rd();
for(i=;i<=N;i++){
rg[i][]=lower_bound(pos+,pos+N+,pos[i]-r[i])-pos;
rg[i][]=upper_bound(pos+,pos+N+,pos[i]+r[i])-pos-;
// printf("%d %d %d\n",i,rg[i][0],rg[i][1]);
}
build(root,,N);
for(i=;i<=N;i++){
conn(root,,N,rg[i][],i-,id[i]);
conn(root,,N,i+,rg[i][],id[i]);
}
for(i=;i<=pct;i++){
if(!dfn[i]) tarjan(i);
}
for(i=;i<=nct;i++){
for(j=hh[i];j;j=hav[j]){
for(k=egh[j];k;k=eg[k][]){
int bb=bel[eg[k][]];if(bb==i) continue;
if(!to[bb]) adeg2(i,bb),to[bb]=;
}
} for(j=hh[i];j;j=hav[j]){
for(k=egh[j];k;k=eg[k][]){
int bb=bel[eg[k][]];
to[bb]=;
}
}
}
int nn=;
for(i=;i<=nct;i++){
if(!ine[i]) q.push(i);
}
while(!q.empty()){
int p=q.front();q.pop();
rk[++nn]=p;
for(i=egh2[p];i;i=eg2[i][]){
int b=eg2[i][];
if(--ine[b]==) q.push(b);
} }
for(i=nct;i;i--){
int p=rk[i];
for(j=egh2[p];j;j=eg2[j][]){
int b=eg2[j][];
val[p]+=val[b];
}
}
ll ans=;
for(i=;i<=N;i++){
ans=(ans+1ll*i*val[bel[id[i]]])%P;
}
printf("%lld\n",ans);
return ;
}
上一篇:python获取linux指定进程名的pid


下一篇:mybatis10 实现类代理对象开发