bzoj 5017 [Snoi2017]炸弹

题面

https://www.lydsy.com/JudgeOnline/problem.php?id=5017

题解

如果数据范围小一点那么就缩点然后跑一个基础的DAG上的dp就好了

但是边数是$O(n^2)$的所以就会炸

然后发现题目的特殊性

每一个点连向的点是连续的换言之就是每个点和一个连续的段连上了一条边

那么我们把段拆开用类似线段树的做法拆成log个小段然后把这个点与这些小段连边即可

记得把每个段向它的儿子连上边

这样点数和边数都是$O(n log n)$ 就可以了

Code

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 
  5 ll read(){
  6     ll x=0,f=1;char c=getchar();
  7     while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
  8     while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
  9     return x*f;
 10 }
 11 
 12 const int mod=1e9+7;
 13 const int maxn=500500;
 14 int n,nwn;
 15 ll pos[maxn],rad[maxn];
 16 struct Node{
 17     int l,r;
 18 } tr[maxn*4];
 19 
 20 int dy[maxn];
 21 
 22 inline bool pd(int a,int b){
 23     return abs(pos[a]-pos[b])<=rad[a];
 24 }
 25 
 26 int head[maxn*5],nxt[maxn*20],to[maxn*20],cnt;
 27 int rhead[maxn*5],rnxt[maxn*20],rto[maxn*20],rcnt;
 28 
 29 inline void add_edge(int a,int b){
 30     to[++cnt]=b;
 31     nxt[cnt]=head[a];
 32     head[a]=cnt;
 33     rto[++rcnt]=a;
 34     rnxt[rcnt]=rhead[b];
 35     rhead[b]=rcnt;
 36 }
 37 
 38 void build(int i,int l,int r){
 39     tr[i].l=l,tr[i].r=r;
 40     nwn=max(nwn,i);
 41     if(l==r){
 42         dy[l]=i;return;
 43     }
 44     int md=(l+r)>>1;
 45     build(i*2,l,md);
 46     build(i*2+1,md+1,r);
 47     add_edge(i,i*2);
 48     add_edge(i,i*2+1);
 49 }
 50 
 51 inline void work(int ind,int i,int l,int r){
 52     if(tr[i].l>r || tr[i].r<l) return;
 53     if(tr[i].l>=l && tr[i].r<=r){
 54         add_edge(dy[ind],i);
 55         return;
 56     }
 57     work(ind,i*2,l,r);
 58     work(ind,i*2+1,l,r);
 59 }
 60 
 61 int vis[maxn*4];
 62 int seq[maxn*4],tot;
 63 int col;
 64 
 65 void dfs1(int nw){
 66     vis[nw]=1;
 67     for(int i=rhead[nw];i;i=rnxt[i]){
 68         int v=rto[i];
 69         if(vis[v]) continue;
 70         dfs1(v);
 71     }
 72     seq[++tot]=nw;
 73 }
 74 
 75 void dfs2(int nw){
 76     vis[nw]=col;
 77     for(int i=head[nw];i;i=nxt[i]){
 78         int v=to[i];
 79         if(vis[v]) continue;
 80         dfs2(v);
 81     }
 82 }
 83 
 84 int sz[maxn*4];
 85 int ans[maxn*4];
 86 bool vis2[maxn*4];
 87 
 88 void dfs3(int nw){
 89     if(ans[vis[nw]]==0) ans[vis[nw]]=sz[vis[nw]];
 90     vis2[nw]=1;
 91     for(int i=head[nw];i;i=nxt[i]){
 92         int v=to[i];
 93         if(vis2[v]) continue;
 94         dfs3(v);
 95         if(vis[v]!=vis[nw])
 96             ans[vis[nw]]+=ans[vis[v]];
 97     }
 98 }
 99 
100 int main(){
101     #ifdef LZT
102     freopen("in","r",stdin);
103     #endif
104     n=read();
105     build(1,1,n);
106     for(int i=1;i<=n;i++)
107         pos[i]=read(),rad[i]=read();
108     int l,r;
109     for(int i=1;i<=n;i++){
110         int L=1,R=i;
111         while(L<=R){
112             int md=(L+R)>>1;
113             if(pos[i]-pos[md]>rad[i]) L=md+1;
114             else R=md-1,l=md;
115         }
116         L=i,R=n;
117         while(L<=R){
118             int md=(L+R)>>1;
119             if(pos[md]-pos[i]>rad[i]) R=md-1;
120             else L=md+1,r=md;
121         }
122         work(i,1,l,r);
123     }
124     
125     for(int i=1;i<=nwn;i++){
126         if(tr[i].l==0) continue;
127         if(!vis[i]) dfs1(i);
128     }
129     memset(vis,0,sizeof(vis));
130     
131     for(int i=tot;i>=1;i--)
132         if(!vis[seq[i]]) ++col,dfs2(seq[i]);
133     
134     for(int i=1;i<=nwn;i++) if(tr[i].l && tr[i].l==tr[i].r) sz[vis[i]]++;
135     dfs3(1);
136     
137     ll res=0;
138     for(int i=1;i<=nwn;i++){
139         if(tr[i].l<tr[i].r) continue;
140         res+=tr[i].l*1ll*ans[vis[i]]%mod;
141         res%=mod;
142     }
143     printf("%lld
",res);
144     
145     return 0;
146 }
147 
148 /*
149 4
150 1 1
151 5 1
152 6 5
153 15 15
154 */

View Code

Review

动机?

首先缩点+dp是显然的

然后我就没有想到怎么优化

其实也不难想啊就是要把连续的一段点转化成几个点也就是区间->几个点 那么就上线段树嘛

然后写的时候注意总点数的处理

按照我的线段树写法一棵树中 最小编号到最大编号之间不连续也就是有一些编号不对应任何点

这样在遍历所有点的时候要判断一下当前编号是否存在