萌新刚学OI,求助求助哇
查看原帖
萌新刚学OI,求助求助哇
111275
暴力的大少爷楼主2020/5/7 16:28

第一,第二个WA了,不知道为什么???

#include <bits/stdc++.h>
#define ll long long
#define MAXN 500010
#define mod 1000000007
using namespace std;
struct edge{int v,nxt;}E[MAXN*25];
int p[MAXN<<2],eid=0;
void init(){
	memset(p,-1,sizeof(p));
	eid=0;
}
void insert(int u,int v){
	//printf("-%d %d\n",u,v);
	E[eid].v=v;
	E[eid].nxt=p[u];
	p[u]=eid++;
}
struct Tree{int l,r;}T[MAXN<<2];
int to[MAXN],lc[MAXN<<2],rc[MAXN<<2],tot=0,rt;
void build(int &id,int l,int r){
	id=++tot;T[id].l=l,T[id].r=r;
	if(l==r){
		to[l]=id;
		return;
	}
	int mid=(l+r)>>1;
	build(lc[id],l,mid);
	build(rc[id],mid+1,r);
	insert(id,lc[id]);
	insert(id,rc[id]);
}
void update(int id,int l,int r,int x,int y,int v){
	if(x<=l && r<=y){
		insert(v,id);
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update(lc[id],l,mid,x,y,v);
	if(y>mid) update(rc[id],mid+1,r,x,y,v);
}
int n;
ll x[MAXN],R[MAXN];

int dfn[MAXN<<2],low[MAXN<<2],TIM=0,S[MAXN<<2],tp=0,bel[MAXN<<2],LL[MAXN<<2],RR[MAXN<<2],scc_cnt=0;
bool vis[MAXN<<2];
void tarjan(int u){
	dfn[u]=low[u]=++TIM;
	S[++tp]=u;vis[u]=true;
	for(register int i=p[u];i!=-1;i=E[i].nxt){
		int v=E[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		++scc_cnt;
		LL[scc_cnt]=0x3f3f3f3f,RR[scc_cnt]=0;
		while(true){
			int x=S[tp--];
			LL[scc_cnt]=min(LL[scc_cnt],T[x].l);
			RR[scc_cnt]=max(RR[scc_cnt],T[x].r);
			bel[x]=scc_cnt;
			if(x==u) break;
		}
	}
}
vector<int> vec[MAXN<<2];
int deg[MAXN<<2];
void topu(int u){
	queue<int> q;
	for(register int i=1;i<=tot;++i) if(deg[i]==0) q.push(i);
	while(!q.empty()){
		int u=q.front(),len=vec[u].size();
		for(register int i=0;i<len;++i){
			int v=vec[u][i];
			LL[v]=min(LL[v],LL[u]);
			RR[v]=max(RR[v],RR[u]);
			deg[v]--;
			if(deg[v]==0) q.push(v);
		}
	}
}
int main(){
	scanf("%d",&n);init();build(rt,1,n);
	for(register int i=1;i<=n;++i) scanf("%lld%lld",&x[i],&R[i]);
	for(register int i=1;i<=n;++i){
		int l,r,mid,resl,resr;
		l=1,r=i;
		while(l<=r){
			mid=(l+r)>>1;
			if(x[mid] >= x[i]-R[i]) resl=mid,r=mid-1;
			else l=mid+1;
		}
		l=i,r=n;
		while(l<=r){
			mid=(l+r)>>1;
			if(x[mid] <= x[i]+R[i]) resr=mid,l=mid+1;
			else r=mid-1;
		}
		update(1,1,n,resl,resr,to[i]);
	}tarjan(1);
	for(register int u=1;u<=tot;++u){
		for(register int i=p[u];i!=-1;i=E[i].nxt){
			int v=E[i].v;
			if(bel[u]==bel[v]) continue;
			vec[v].push_back(u);deg[u]++;
		}
	}
	int ans=0;
	for(register int i=1;i<=n;++i) ans=(ans+1ll*i*(RR[bel[to[i]]]-LL[bel[to[i]]]+1)%mod)%mod;
	printf("%d\n",ans);
	return 0;
}
2020/5/7 16:28
加载中...