萌新86求助,WA 1、2两个点
查看原帖
萌新86求助,WA 1、2两个点
223362
Peter3245127684楼主2020/7/8 20:20
#include<bits/stdc++.h>
#define ll long long
#define N 500010
using namespace std;
const ll MOD=1e9+7;
struct Node
{
	int l,r;
}tree[N*8];
struct node
{
	int to,w,nxt;
}edge[N*20]; 
int n,tot,cnt,deep,Col;
ll ans;
int head[N<<2],dfn[N<<2],low[N<<2],seg[N<<2],col[N<<2],vis[N<<2],lef[N<<2],rig[N<<2],L[N<<2],R[N<<2];
ll x[N],r[N];
stack<int> s;
vector<pair<int,int> > G;
template <typename T>
inline int read(T &x)
{
	T flg=1;x=0;
	char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') flg=-flg;ch=getchar();}
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*=flg;
}
template <typename T>
inline void write(T x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T>
inline void writeln(T x) {write(x);puts("");}
template <typename T>
inline void writesp(T x) {write(x);putchar(' ');}
inline ll min(const ll &x,const ll &y) {return x<y?x:y;}
inline ll max(const ll &x,const ll &y) {return x>y?x:y;}
inline void add(int u,int v)
{
	edge[++cnt].to=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
inline int ls(const int &x) {return x<<1;}
inline int rs(const int &x) {return x<<1|1;}
inline void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r) {seg[i]=l;return;}
	int mid=l+r>>1;
	seg[i]=++tot;
	lef[seg[i]]=l;rig[seg[i]]=r;
	build(ls(i),l,mid);
	build(rs(i),mid+1,r);
	add(seg[i],seg[ls(i)]);add(seg[i],seg[rs(i)]);
	G.push_back(make_pair(seg[i],seg[ls(i)]));
	G.push_back(make_pair(seg[i],seg[rs(i)]));
}
inline void modify(int i,int l,int r,int u)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	  {
	  	add(u,seg[i]);
	  	G.push_back(make_pair(u,seg[i]));
	  	return;
	  }
	int mid=tree[i].l+tree[i].r>>1;
	if(l<=mid) modify(ls(i),l,r,u);
	if(r>mid) modify(rs(i),l,r,u);
}
inline void Scc()
{
	col[s.top()]=Col;
	L[Col]=min(L[Col],lef[s.top()]);
	R[Col]=max(R[Col],rig[s.top()]);
	vis[s.top()]=0;s.pop();
}
inline void Tarjan(int u)
{
	dfn[u]=low[u]=++deep;
	s.push(u);
	vis[u]=1;
	for(register int i=head[u];i;i=edge[i].nxt)
	  {
	  	int v=edge[i].to;
	  	if(!dfn[v])
	  	  {
	  	  	Tarjan(v);
	  	  	low[u]=min(low[u],low[v]);
		  }
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	  }
	if(low[u]==dfn[u])
	  {
	  	L[++Col]=n+1;
	  	while(s.top()^u) Scc();
	  	Scc();
	  }
}
inline void init()
{
	cnt=0;
	memset(head,0,sizeof(head));
	memset(edge,0,sizeof(edge));
}
inline void dfs(int u)
{
	vis[u]=1;
	for(register int i=head[u];i;i=edge[i].nxt)
	  {
	  	int v=edge[i].to;
	  	if(!vis[v]) dfs(v);
	  	lef[u]=min(lef[u],lef[v]);
	  	rig[u]=max(rig[u],rig[v]);
	  }
}
signed main()
{
	read(n);
	tot=n;
	for(register int i=1;i<=n;++i)
	  read(x[i]),read(r[i]);
	build(1,1,n);
	for(register int i=1;i<=n;++i)
	  {
	  	int Lpos=lower_bound(x+1,x+n+1,x[i]-r[i])-x;
	  	int Rpos=upper_bound(x+1,x+n+1,x[i]+r[i])-x-1;
	  	lef[i]=Lpos;rig[i]=Rpos;
	  	modify(1,Lpos,Rpos,i);
	  }
	for(register int i=1;i<=tot;++i)
	  if(!dfn[i]) Tarjan(i);
	init();
	for(register int i=0;i<G.size();++i)
	  {
	  	int u=G[i].first;
	  	int v=G[i].second;
	  	if(col[u]==col[v]) continue;
	  	add(col[u],col[v]);
	  }
	for(register int i=1;i<=Col;++i)
	  if(!vis[i]) dfs(i);
	for(register int i=1;i<=n;++i)
	  ans=(ans+1LL*(R[col[i]]-L[col[i]]+1)*i%MOD)%MOD;
	write(ans);
	return 0;
}
2020/7/8 20:20
加载中...