这题原文地址
题目描述
在一条直线上有 N 个炸弹，每个炸弹的坐标是 Xi，爆炸半径是 Ri，当一个炸弹爆炸时，如果另一个炸弹所在位置 Xj 满足：
Xi−Ri≤Xj≤Xi+Ri,那么，该炸弹也会被引爆。
现在，请你帮忙计算一下，先把第 i 个炸弹引爆，将引爆多少个炸弹呢？
输入
第一行，一个数字 N，表示炸弹个数。
第 2∼N+1行，每行 2 个数字，表示 Xi，Ri，保证 Xi 严格递增。
N≤500000
−10^18≤Xi≤10^18
0≤Ri≤2×10^18
输出
一个数字，表示Sigma(i*炸弹i能引爆的炸弹个数),1<=i<=N mod10^9+7。
样例输入
4
1 1
5 1
6 5
15 15
样例输出
32
这题看到之后肯定有个非常显然的建图方法 那就是 向所有他能连接的点建图 但是这样显然复杂度爆炸 那么就是线段树的优化建图了 这题我本以为2*(10^18)会非常烦人 其实ll的大小大概是9*(10^18)这么大 完全不必担心 具体的题解 还是看另一道比较相似的题吧http://www.elijahqi.win/2017/12/15/nkoi-round-8-%e7%aa%81%e7%84%b6%e7%82%b9%e4%ba%ae%e7%9a%84%e6%95%85%e9%9a%9c%e7%81%af/
本人真的特别菜 可能代码会有点丑丑的qwq
#include<map>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000000
#define mod 1000000007
#define pa pair<int,int>
#define ll long long
using namespace std;
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline ll read(){
ll x=0;int f=1;char ch=gc();
while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
return x*f;
}
map<pa,int>mm;
struct node{
int x,y,next;
}data[20000000];
int num,h[N],n,tot,w[550000],root;ll a[550000],l[550000],ans,range1[N],range2[N];
inline void insert1(int x,int y){
data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].x=x;
}
stack<int>q;int dfn[N],low[N],stackf[N],s,b[N],cnt[N],in[N];ll min1[N],max1[N];
void tarjan(int x){
dfn[x]=low[x]=++num;stackf[x]=1;q.push(x);
for(int i=h[x];i;i=data[i].next){
int y=data[i].y;
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if(stackf[y]) low[x]=min(low[x],dfn[y]);
}
if (dfn[x]==low[x]){
s++;int y;
do{
y=q.top();q.pop();stackf[y]=0;b[y]=s;min1[s]=min(min1[s],range1[y]);max1[s]=max(max1[s],range2[y]);
}while(y!=x);
}
}
struct node1{
int left,right;
}tree[N];
void build(int &x,int l,int r){
x=++tot;
range1[x]=l;range2[x]=r;
if (l==r) {w[l]=x;return;}
int mid=l+r>>1;build(tree[x].left,l,mid);insert1(x,tree[x].left);
build(tree[x].right,mid+1,r);insert1(x,tree[x].right);
}
inline void insert2(int x,int l,int r,int l1,int r1,int p){
if (l1<=l&&r1>=r){if(p==x) return;insert1(p,x);return;}
int mid=l+r>>1;
if (l1<=mid) insert2(tree[x].left,l,mid,l1,r1,p);
if (r1>mid) insert2(tree[x].right,mid+1,r,l1,r1,p);
}
void print(int x){
if (tree[x].left) print(tree[x].left);
printf("%d %d %d\n",x,range1[x],range2[x]);
if (tree[x].right) print(tree[x].right);
}
int main(){
freopen("bzoj5017.in","r",stdin);
ll minx=1LL<<62,maxx=-minx;
n=read();for (int i=1;i<=n;++i) min1[i]=minx,max1[i]=-minx;
for (int i=1;i<=n;++i) a[i]=read(),l[i]=read(),maxx=max(a[i],(long long)maxx),minx=min((long long)minx,a[i]);
build(root,1,n);//print(root);
for (int i=1;i<=n;++i){
ll l1=max(minx,a[i]-l[i]),r1=min(maxx,a[i]+l[i]);
int posl=lower_bound(a+1,a+n+1,l1)-a,posr=upper_bound(a+1,a+n+1,r1)-a-1;
// printf("%d %d\n",posl,posr);
insert2(root,1,n,posl,posr,w[i]);
}
int nm=num;num=0;
// for (int i=1;i<=nm;++i) printf("%d %d\n",data[i].x,data[i].y);
for (int i=1;i<=tot;++i) if (!dfn[i]) tarjan(i);num=0;memset(h,0,sizeof(h));
// for (int i=1;i<=n;++i) printf("%d ",w[i]);printf("\n");
//for (int i=1;i<=tot;++i) printf("%d ",b[i]);printf("\n");
//for (int i=1;i<=s;++i) printf("%d %d %d\n",i,min1[i],max1[i]);printf("\n");
for (int i=1;i<=nm;++i){
int x=data[i].x,y=data[i].y;
if (b[x]!=b[y]&&!mm[make_pair(b[y],b[x])]){
insert1(b[y],b[x]);in[b[x]]++;mm[make_pair(b[y],b[x])]=1;
}
}queue<int>qq;
for (int i=1;i<=s;++i) if (!in[i]) qq.push(i);
while(!qq.empty()){
int x=qq.front();qq.pop();
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;min1[y]=min(min1[y],min1[x]);max1[y]=max(max1[y],max1[x]);
if (--in[y]==0) qq.push(y);
}
}
for (int i=1;i<=n;++i) ans=(ll)(max1[b[w[i]]]-min1[b[w[i]]]+1)%mod*i%mod+ans,ans%=mod;printf("%lld",ans);
return 0;
}