P5025 [SNOI2017] 炸弹

~~~~~      P5025 [SNOI2017] 炸弹 ~~~~~      总题单链接

思路

~~~~~      把每个点与其爆炸范围内的点连边，用线段树优化建图可以做到 $O(N\ast log(N))$。

~~~~~      发现在同一个连通块里的点可以互相到达，所以缩点。

~~~~~      所点后 $DP$ 求得每个连通块能到达的左右端点（也可以用拓扑排序或搜索，但 $DP$ 码量最少），这里给出 $DP$ 过程的代码：

for(ll u=1;u<=tr.tot;u++)for(ll v:eg[u])if(scc[u]!=scc[v])ng[scc[v]].push_back(scc[u]);for(ll i=1;i<=tr.tot;i++)dp[i]={INF,-INF};for(ll i=1;i<=n;i++)dp[scc[i]]={min(dp[scc[i]].fir,i),max(dp[scc[i]].sec,i)};for(ll u=1;u<=cnt;u++){for(ll v:ng[u])dp[v]={min(dp[v].fir,dp[u].fir),max(dp[v].sec,dp[u].sec)};}

代码

#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define MOD 1000000007
#define INF 0x3f3f3f3f3f3f3f
using namespace std;vector<ll>eg[25000005];
ll n,g[500005],r[500005];class{
public:ll tot=n;struct Point{ll L,R,id;}po[2000005];void build(ll x=1,ll y=n,ll p=1){po[p]={x,y,++tot};if(x==y){eg[po[p].id].push_back(x);return;}ll mid=(x+y)>>1;build(x,mid,p<<1);build(mid+1,y,p<<1|1);eg[po[p].id].push_back(po[p<<1].id);eg[po[p].id].push_back(po[p<<1|1].id);}void query(ll wc,ll x,ll y,ll p=1){if(po[p].R<x||po[p].L>y)return;if(po[p].L>=x&&po[p].R<=y){eg[wc].push_back(po[p].id);return;}query(wc,x,y,p<<1);query(wc,x,y,p<<1|1);}
}tr;class{
public:ll dfn[2500005],low[2500005],tot;ll scc[2500005],siz[2500005],cnt;ll stk[2500005],ins[2500005],top;vector<ll>ng[2500005];pair<ll,ll>dp[200005];void Tarjan(ll p){dfn[p]=low[p]=++tot;stk[++top]=p;ins[p]=1;for(ll v:eg[p]){if(!dfn[v]){Tarjan(v);low[p]=min(low[p],low[v]);}else if(ins[v])low[p]=min(low[p],dfn[v]);}if(dfn[p]==low[p]){cnt++;while(1){ll v=stk[top--];ins[v]=0;scc[v]=cnt;if(v<=n)siz[cnt]++;if(v==p)break;}}}void work(){for(ll i=1;i<=tr.tot;i++)if(!dfn[i])Tarjan(i);for(ll u=1;u<=tr.tot;u++)for(ll v:eg[u])if(scc[u]!=scc[v])ng[scc[v]].push_back(scc[u]);for(ll i=1;i<=tr.tot;i++)dp[i]={INF,-INF};for(ll i=1;i<=n;i++)dp[scc[i]]={min(dp[scc[i]].fir,i),max(dp[scc[i]].sec,i)};for(ll u=1;u<=cnt;u++){for(ll v:ng[u])dp[v]={min(dp[v].fir,dp[u].fir),max(dp[v].sec,dp[u].sec)};}ll ans=0;for(ll i=1;i<=n;i++){(ans+=i*(dp[scc[i]].sec-dp[scc[i]].fir+1)%MOD)%=MOD;}cout<<ans;}
}TJ;signed main(){ios::sync_with_stdio(false);cin>>n;tr.tot=n;tr.build();for(ll i=1;i<=n;i++)cin>>g[i]>>r[i];for(ll i=1;i<=n;i++){ll L=lower_bound(g+1,g+1+n,g[i]-r[i])-g;ll R=upper_bound(g+1,g+1+n,g[i]+r[i])-g-1;if(L<=i-1)tr.query(i,L,i-1);if(i+1<=R)tr.query(i,i+1,R);}TJ.work();return 0;
}