本文共 4412 字，大约阅读时间需要 14 分钟。
Description
在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足：
Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。 现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？ Input第一行，一个数字 N，表示炸弹个数。
第 2∼N+1行，每行 2 个数字，表示 Xi，Ri，保证 Xi 严格递增。 N≤500000 −10^18≤Xi≤10^18 0≤Ri≤2×10^18 Output一个数字，表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。
Sample Input4
1 1
5 1
6 5
15 15
Sample Output32
这题是哈老师给的神题
然后他给了我一个有一点点复杂的做法 于是帅爷爷就又教了我一个方法 然后我在今天做操的时候仔细斟酌了一下，觉得很对，于是就A了首先，我们可以建图。。
就是每个点对他可以炸到的范围连一条边。。 然后对于每个点dfs一次，他可以从他连的点得到新的l和r 这里要注意的时，虽然说每个点必须要访问，更新答案，这样才能确保他的答案是对的 然后由于可能边数很大，于是要用线段树优化建图，就好了CODE:
#include#include #include #include #include using namespace std;typedef long long LL;const LL N=2000010;int n;LL X[N],R[N];const int MOD=1e9+7;struct qq{ int x,y,last;}s[N*8];int Num,last[N];int ll[N],rr[N];void init (int x,int y){ Num++; s[Num].x=x;s[Num].y=y; s[Num].last=last[x]; last[x]=Num; return ;}void Ins (){ Num=0;memset(last,-1,sizeof(last)); scanf("%d",&n); for (int u=1;u<=n;u++) scanf("%lld%lld",&X[u],&R[u]);}struct qr{ int l,r; int s1,s2;}tr[N];int num;int pos[N];void bt (int l,int r){ int a=++num; tr[a].l=l;tr[a].r=r; ll[a]=l;rr[a]=r; if (l==r) { pos[l]=a; return ; } int mid=(l+r)>>1; tr[a].s1=num+1;bt(l,mid); tr[a].s2=num+1;bt(mid+1,r); init(a,tr[a].s1);init(a,tr[a].s2);}void Link (int now,int l,int r,int x){ if (tr[now].l==l&&tr[now].r==r) { init(x,now); return ; } int mid=(tr[now].l+tr[now].r)>>1; int s1=tr[now].s1,s2=tr[now].s2; if (r<=mid) Link(s1,l,r,x); else if (l>mid) Link(s2,l,r,x); else Link(s1,l,mid,x),Link(s2,mid+1,r,x);}void Bt (){ num=0;bt(1,n); //for (int u=1;u<=n;u++) printf("%d ",pos[u]); for (int u=1;u<=n;u++) { int l=1,r=u; int p; while (l<=r) { int mid=(l+r)>>1; if (X[mid]+R[u]>=X[u]) {p=mid;r=mid-1;} else l=mid+1; } if (p!=u) Link(1,p,u-1,pos[u]); // printf("%d %d %d\n",p,u-1,pos[u]); l=u;r=n; while (l<=r) { int mid=(l+r)>>1; if (X[mid]-R[u]<=X[u]) {p=mid;l=mid+1;} else r=mid-1; } if (p!=u) Link(1,u+1,p,pos[u]); // printf("%d %d %d\n",u+1,u-1,pos[u]); }}bool vis[N];int mymax (int x,int y){ return x>y?x:y;}int mymin (int x,int y){ return x
Update 9.9 方法被人hack了。。
其实是bzoj的数据太水了。。 上面的方法其实有很大的漏洞，也跑不出来。。 其实有环的时候就会有很大的问题。。 这个自己对拍一下，就应该能找到了 所以我们要用强连通缩点，就可以跑过去了。。新的CODE:
#include#include #include #include #include using namespace std;typedef long long LL;const int N=2000010;int n;LL X[N],R[N];const int MOD=1e9+7;struct qq{ int x,y,last;}s[N*8];int Num,last[N];int ll[N],rr[N];void init (int x,int y){ Num++; s[Num].x=x;s[Num].y=y; s[Num].last=last[x]; last[x]=Num; return ;}void Ins (){ Num=0;memset(last,-1,sizeof(last)); scanf("%d",&n); for (int u=1;u<=n;u++) scanf("%lld%lld",&X[u],&R[u]);}struct qr{ int l,r; int s1,s2;}tr[N];int num;int pos[N];void bt (int l,int r){ int a=++num; tr[a].l=l;tr[a].r=r; ll[a]=l;rr[a]=r; if (l==r) { pos[l]=a; return ; } int mid=(l+r)>>1; tr[a].s1=num+1;bt(l,mid); tr[a].s2=num+1;bt(mid+1,r); init(a,tr[a].s1);init(a,tr[a].s2);}void Link (int now,int l,int r,int x){ if (tr[now].l==l&&tr[now].r==r) { init(x,now); return ; } int mid=(tr[now].l+tr[now].r)>>1; int s1=tr[now].s1,s2=tr[now].s2; if (r<=mid) Link(s1,l,r,x); else if (l>mid) Link(s2,l,r,x); else Link(s1,l,mid,x),Link(s2,mid+1,r,x);}void Bt (){ num=0;bt(1,n); //for (int u=1;u<=n;u++) printf("%d ",pos[u]); for (int u=1;u<=n;u++) { int l=1,r=u; int p; while (l<=r) { int mid=(l+r)>>1; if (X[mid]+R[u]>=X[u]) {p=mid;r=mid-1;} else l=mid+1; } if (p!=u) Link(1,p,u-1,pos[u]); // printf("%d %d %d\n",p,u-1,pos[u]); l=u;r=n; while (l<=r) { int mid=(l+r)>>1; if (X[mid]-R[u]<=X[u]) {p=mid;l=mid+1;} else r=mid-1; } if (p!=u) Link(1,u+1,p,pos[u]); // printf("%d %d %d\n",u+1,u-1,pos[u]); }}bool vis[N];int mymax (int x,int y){ return x>y?x:y;}int mymin (int x,int y){ return x
转载地址：http://cfcq.baihongyu.com/