容易想到每个炸弹向其能引爆的炸弹连边,tarjan缩点后bitset传递闭包。进一步发现每个炸弹能直接引爆的炸弹是一段连续区间,于是线段树优化建图即可让边的数量降至O(nlogn)。再冷静一下由于能间接引爆的炸弹也是一段连续区间,传递闭包时只要记录可达点的左右端点即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 500010
#define M N<<2
#define ll long long
#define P 1000000007
ll read()
{
ll x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,p[M],dfn[M],low[M],stk[M],Set[M],L[M],R[M],root,t,cnt,top,tot,ans=;
bool flag[M];
ll a[N],b[N];
struct data{int to,nxt;
}edge[M<<];
struct data2{int l,r;
}tree[M];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}
void build(int &k,int l,int r)
{
if (l==r) {k=l;return;}
k=++cnt;
int mid=l+r>>;
build(tree[k].l,l,mid);
build(tree[k].r,mid+,r);
addedge(k,tree[k].l),addedge(k,tree[k].r);
}
void add(int k,int l,int r,int x,int y,int p)
{
if (l==x&&r==y) {addedge(p,k);return;}
int mid=l+r>>;
if (y<=mid) add(tree[k].l,l,mid,x,y,p);
else if (x>mid) add(tree[k].r,mid+,r,x,y,p);
else add(tree[k].l,l,mid,x,mid,p),add(tree[k].r,mid+,r,mid+,y,p);
}
void tarjan(int k)
{
dfn[k]=low[k]=++cnt;stk[++top]=k;flag[k]=;
for (int i=p[k];i;i=edge[i].nxt)
if (!dfn[edge[i].to]) tarjan(edge[i].to),low[k]=min(low[k],low[edge[i].to]);
else if (flag[edge[i].to]) low[k]=min(low[k],dfn[edge[i].to]);
if (dfn[k]==low[k])
{
tot++;L[tot]=n+,R[tot]=;
while (stk[top]!=k)
{
Set[stk[top]]=tot;
if (stk[top]<=n) L[tot]=min(L[tot],stk[top]),R[tot]=max(R[tot],stk[top]);
flag[stk[top]]=;
top--;
}
Set[k]=tot;if (k<=n) L[tot]=min(L[tot],k),R[tot]=max(R[tot],k);flag[k]=,top--;
}
}
namespace newgraph
{
int p[M]={},degree[M]={},q[M],t=;
struct data{int to,nxt;}edge[M<<];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;degree[y]++;}
void topsort()
{
int head=,tail=;
for (int i=;i<=tot;i++) if (!degree[i]) q[++tail]=i;
while (tail<tot)
{
int x=q[++head];
for (int i=p[x];i;i=edge[i].nxt)
{
degree[edge[i].to]--;
if (!degree[edge[i].to]) q[++tail]=edge[i].to;
}
}
}
void dp()
{
for (int i=tot;i>=;i--)
{
int x=q[i];
for (int j=p[x];j;j=edge[j].nxt)
L[x]=min(L[x],L[edge[j].to]),R[x]=max(R[x],R[edge[j].to]);
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj5017.in","r",stdin);
freopen("bzoj5017.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<=n;i++) a[i]=read(),b[i]=read();
cnt=n;
build(root,,n);
for (int i=;i<=n;i++)
{
int x,y;
int l=,r=i;
while (l<=r)
{
int mid=l+r>>;
if (a[i]-b[i]<=a[mid]) x=mid,r=mid-;
else l=mid+;
}
l=i,r=n;
while (l<=r)
{
int mid=l+r>>;
if (a[i]+b[i]>=a[mid]) y=mid,l=mid+;
else r=mid-;
}
add(root,,n,x,y,i);
}
t=cnt;cnt=;
for (int i=;i<=t;i++) if (!dfn[i]) tarjan(i);
for (int k=;k<=t;k++)
for (int i=p[k];i;i=edge[i].nxt)
if (Set[k]!=Set[edge[i].to]) newgraph::addedge(Set[k],Set[edge[i].to]);
newgraph::topsort();
newgraph::dp();
for (int i=;i<=n;i++) ans=(ans+1ll*i*(R[Set[i]]-L[Set[i]]+))%P;
cout<<ans;
return ;
}

最新文章

  1. Linux 执行文件查找命令 which 详解
  2. python base64的加密与解密
  3. WORD 粘贴代码 不检查语法
  4. 修改ubuntu中usr文件夹的权限后,sudo后出现sudo:must be setuid root问题的解决方案
  5. Mysql 只导出数据,不包含表结构
  6. 屏幕实战效果解析:IPS/TFT/AMOLED/SLCD
  7. js和 jquery对象
  8. guava中eventbus注解使用
  9. BZOJ3963: [WF2011]MachineWorks
  10. 移动端日历控件 mobiscroll 的简单使用、参数设置
  11. Mysql--存储引擎(MyISam &amp; InnoDB)
  12. qt手写输入法资料
  13. word中一页中添加两种不同的页码
  14. NVCC src/caffe/util/math_functions.cu
  15. 【jquery采坑】Ajax配合form的submit提交(微擎表单提交,ajax验证,submit提交)
  16. 用代码打开通知中心(statusbar、通知栏、消息中心)
  17. 关于卸载vmware后如何删除VMware Network Adapter VMnet1虚拟网卡
  18. 使用nginx+dnsmasq解决同IP不同端口Session冲突问题
  19. java线程的常用方法
  20. [EXT JS]&quot;hasMany&quot; association on ExtJS 4.1.1a

热门文章

  1. C#基础之委托
  2. day 11 名片管理系统
  3. 1563: [NOI2009]诗人小G
  4. 二分查找的C#实现
  5. 【word基础】如何取消word首字母大写
  6. Django之视图系统
  7. Mongodb大数据语法大全
  8. Vue-lazyload 的使用
  9. [shell] 循环判断输入值
  10. python序列成员资格