8分求助
查看原帖
8分求助
377969
george0929楼主2024/8/1 15:45
#include<bits/stdc++.h>
using namespace std;
int n;
long long x[500005],y[500005];
int pos[500005],in[2000005],L[2000005],R[2000005];
vector<int> V[2000005],G[2000005],F[2000005];
void buildin(int p,int l,int r){
	if(l==r){
		pos[l]=p;
		return;
	}
	int mid=(l+r)/2;
	buildin(p*2,l,mid);
	buildin(p*2+1,mid+1,r);
	V[p].push_back(p*2);
	V[p].push_back(p*2+1);
}
void merge(int p,int l,int r,int qpos,int ql,int qr){
	if(ql<=l&&r<=qr){
		V[qpos].push_back(p);
		return;
	}
	int mid=(l+r)/2;
	if(mid>=ql){
		merge(p*2,l,mid,qpos,ql,qr);
	}
	if(mid<qr){
		merge(p*2+1,mid+1,r,qpos,ql,qr);
	}
}
queue<int> Q;
int vis[2000005],lt[2000005],cnt;
stack<int> S;
map<int,int> M[2000005];
void upd(int p,int l,int r){
	L[lt[p]]=min(L[lt[p]],l);
	R[lt[p]]=max(R[lt[p]],r);
	if(l==r){
		return;
	}
	int mid=(l+r)/2;
	upd(p*2,l,mid);
	upd(p*2+1,mid+1,r);
}
void dfs(int u){
	for(int v:V[u]){
		if(!vis[v]){
			vis[v]=1;
			dfs(v);
		}
	}
	S.push(u);
}
void dfs2(int u,int x){
	for(int v:G[u]){
		if(!lt[v]){
			lt[v]=x;
			dfs2(v,x);
		}
	}
}
long long mod=1e9+7;
signed main(){
	memset(L,0x3f,sizeof(L));
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	buildin(1,1,n);
	for(int i=1;i<=n;i++){
		int l=1,r=i-1,res=i;
		while(l<=r){
			int mid=(l+r)/2;
			if(x[i]-x[mid]<=y[i]){
				res=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		if(res!=i) merge(1,1,n,pos[i],res,i-1);
		
		l=i+1,r=n,res=i;
		while(l<=r){
			int mid=(l+r)/2;
			if(x[mid]-x[i]<=y[i]){
				res=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		if(res!=i) merge(1,1,n,pos[i],i+1,res);
	}
	//----------------------
	for(int i=1;i<=2*n;i++){
		for(int j:V[i]){
			G[j].push_back(i);
//			cout<<i<<" -> "<<j<<endl;
		}
	}
	for(int i=1;i<=2*n;i++){
		if(!vis[i]){
			vis[i]=1;
			dfs(i);
		}
	}
	//--------------------
	while(!S.empty()){
		int u=S.top();
		S.pop();
		if(!lt[u]){
			lt[u]=++cnt;
			dfs2(u,cnt);
		}
	} 
	//---------------------------
	for(int i=1;i<=2*n;i++){
		for(int j:V[i]){
			if(lt[i]==lt[j]) continue;
			if(M[lt[i]][lt[j]]) continue;
			M[lt[i]][lt[j]]=1;
			F[lt[j]].push_back(lt[i]);
//			cout<<lt[j]<<"->"<<lt[i]<<endl;
			in[lt[i]]++;
		}
//		cerr<<"::"<<lt[i]<<"\n";
	}
	upd(1,1,n);
	for(int i=1;i<=cnt;i++){
		if(in[i]==0){
			Q.push(i);
		}
//		cout<<L[i]<<" "<<R[i]<<endl;
	}
	//-----------------
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		for(int v:F[u]){
			L[v]=min(L[v],L[u]),R[v]=max(R[v],R[u]);
			in[v]--;
			if(!in[v]){
				Q.push(v);
			}
		}
	}
	//--------------------
	long long ans=0;
	for(int i=1;i<=n;i++){
//		cout<<(R[lt[pos[i]]]-L[lt[pos[i]]]+1)<<endl;
		ans+=1ll*i*(R[lt[pos[i]]]-L[lt[pos[i]]]+1);
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}
/*
5
1 1
2 1
10 1
11 10
19 5
*/
2024/8/1 15:45
加载中...