壶关求助!84pts,借鉴了第二篇题解
查看原帖
壶关求助!84pts,借鉴了第二篇题解
996300
CMY2013楼主2025/1/18 10:51
#include<bits/stdc++.h>

using namespace std;
const int mod=1000000007;
struct node
{
	int l,r;
}a[2000010];

int n,k,nk=0,tot=0,cnt=0,id[2000010],lt[2000010],rt[2000010],dfn[2000010],low[2000010],x[2000010],r[2000010],scc[2000010];
vector<int> vec[2000010],vel[2000010];
bool inst[2000010],vis[2000010];
stack<int> c;
void tarjan(int x)
{
	dfn[x]=low[x]=++tot;
	c.push(x);
	inst[x]=true;
	for(auto o:vec[x])
	{
		if(!dfn[o])
		{
			tarjan(o);
			low[x]=min(low[x],low[o]);
		}
		else if(inst[x]) low[x]=min(low[x],dfn[o]);
	}
	if(dfn[x]==low[x])
	{
		++cnt;
		int y=0;
		do
		{
			y=c.top();
			scc[y]=cnt;
			inst[y]=false;
			lt[cnt]=min(lt[cnt],a[y].l);
			rt[cnt]=max(rt[cnt],a[y].r);
			c.pop();
		}while(y!=x);
	}
}

void build(int l,int r,int u)
{
	a[u].l=l,a[u].r=r;
	nk=max(nk,u);
	if(l==r)
	{
		id[l]=u;
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,u<<1);
	build(mid+1,r,u<<1|1);
	vec[u].push_back(u<<1);
	vec[u].push_back(u<<1|1);
}

void add(int u,int ll,int rr,int l,int r,int v)
{
	if(ll<=l && r<=rr)
	{
		vec[u].push_back(v);
		return;
	}
	int mid=l+r>>1;
	if(ll<=mid) add(u,ll,rr,l,mid,v<<1);
	if(rr>mid) add(u,ll,rr,mid+1,r,v<<1|1);
}

void dfs(int x)
{
	vis[x]=true;
	for(auto o:vel[x])
	{
		if(vis[o])
		{
			lt[x]=min(lt[o],lt[x]); 
			rt[x]=max(rt[o],rt[x]); 
			continue;
		}
		dfs(o);
		lt[x]=min(lt[o],lt[x]); 
		rt[x]=max(rt[o],rt[x]); 
	}
}

signed main()
{
	memset(lt,0x3f,sizeof(lt));
	memset(rt,0xff,sizeof(rt));
	cin>>n;
	for(int i=1;i<=n;i++) cin>>x[i]>>r[i];
	x[n+1]=0x3f3f3f3f3f3f3f3fll;
	build(1,n,1);
	for(int i=1;i<=n;i++)
	{
		int ll=lower_bound(x+1,x+1+n,x[i]-r[i])-x;
        int rr=upper_bound(x+1,x+1+n,x[i]+r[i])-x-1;
        add(id[i],ll,rr,1,n,1);
        a[id[i]].l=ll;
        a[id[i]].r=rr;
	}
	tarjan(1);
	for(int i=1;i<=nk;i++) for(auto x:vec[i]) if(scc[i]!=scc[x]) vel[scc[i]].push_back(scc[x]);
	for(int i=1;i<=cnt;i++)
	{
		sort(vel[i].begin(),vel[i].end());
		unique(vel[i].begin(),vel[i].end());
	}
	for(int i=1;i<=cnt;i++) if(!vis[i]) dfs(i); 
	long long ans=0;
	for(int i=1;i<=n;i++) ans=(ans+i*((rt[scc[id[i]]]-lt[scc[id[i]]]+1)%mod))%mod;
	cout<<ans;
	return 0;
}
/*
hack
in:
5
-55 7
4 108
53 12
67 17
95 15

out:23
*/
2025/1/18 10:51
加载中...