倍增算法 WA #1 #2 求助
查看原帖
倍增算法 WA #1 #2 求助
1030875
born_to_sun楼主2024/5/12 15:39
#include<bits/stdc++.h>
using namespace std;
#define pii pair<long long,int>
int n;
const int mod=1e9+7;
const int N=6e5+5;
long long a[N];
pii st[N][22];
long long x[N];
void st_init1(){
	for(int i=1;i<=n;i++) st[i][0]={x[i]-a[i],i};
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<j)-1>n) break;
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			
		}
	}
}
void st_init2(){
	for(int i=1;i<=n;i++) st[i][0]={x[i]+a[i],i};
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n;i++){
			if(i+(1<<j)-1>n) break;
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
pii q_st(long long l,long long r,int op){
	l=lower_bound(x+1,x+1+n,l)-x;
	long long r0=r;
	r=lower_bound(x+1,x+1+n+1,r)-x;
	if(r0<x[r]) r--;
	int k=log2(r-l+1);
	if(op==0) return min(st[l][k],st[r-(1<<k)+1][k]);
	else return max(st[l][k],st[r-(1<<k)+1][k]);
}
pii f[N][22];
pii ans[N][2];
long long res[N];
long long rs;
void solve1(){
	for(int i=1;i<=n;i++){
		f[i][0]=q_st(x[i]-a[i],x[i]+a[i],0);
		ans[i][0]=f[i][0];
	}
	for(int j=1;j<=21;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=min(f[i][j-1],f[f[i][j-1].second][j-1]);
			ans[i][0]=min(ans[i][0],f[i][j]);
		}
	}
}
void solve2(){
	for(int i=1;i<=n;i++){
		f[i][0]=q_st(x[i]-a[i],x[i]+a[i],1);
		ans[i][1]=f[i][0];
	}
	for(int j=1;j<=21;j++){
		for(int i=1;i<=n;i++){
			f[i][j]=max(f[i][j-1],f[f[i][j-1].second][j-1]);
			ans[i][1]=max(ans[i][1],f[i][j]);
		}
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>a[i];
	x[n+1]=9e18;
	st_init1();
	solve1();
	st_init2();
	solve2();
	for(int i=1;i<=n;i++){
		long long l=ans[i][0].first,r=ans[i][1].first;
		l=lower_bound(x+1,x+1+n,l)-x;
		long long r0=r;
		r=lower_bound(x+1,x+1+n+1,r)-x;
		if(r0<x[r]) r--;
		res[i]=r-l+1;
	}
	for(int i=1;i<=n;i++){
		rs=(rs+res[i]*i)%mod;
	}
	cout<<rs;
	return 0;
}

代码中solve两次是分别计算左端点和右端点,同时计算会MLE

2024/5/12 15:39
加载中...