P4083 - [USACO17DEC] A Pie for a Pie G [선분 수, 최 단 길]

본론
제목 링크:https://www.luogu.com.cn/problem/P4083
제목 의 대의
처음에 A A 와 B B B 는 각각 두 개의 선물 이 있 었 고 선물 마다 두 사람 에 게 서로 다른 가치 가 있 었 다. 처음에 A A 는 B B B 에 게 선물 을 주 었 다.선물 을 받 은 사람 에 게 이 선물 이 그 에 게 v a l val 의 가치 가 있다 면 그 는 그 에 게 [v a l, v a l + d] [val, val + d] [val, val + d] 라 는 범위 안의 선물 을 돌려 줄 것 이다.누 군가 에 게 서 000 원 짜 리 선물 을 받 을 때 까지 멈 추고, A A A 가 주기 시작 한 모든 선물 에 대해 최소한 몇 개의 선물 을 주 고 받 아야 멈 출 수 있 는 지
문제 풀이 의 사고 방향.
우 리 는 사실 매번 한 구간 의 내 연 변 에 대해 최 단 로 를 구 하 는 것 을 발견 할 수 있다.
우 리 는 A A A 와 B B B 에 대해 각각 선분 나 무 를 한 그루 씩 열 고 연결 을 최적화 시 켜 0, 0 의 가치 가 있 는 선물 부터 달 린 다음 에 모든 선물의 최 단 길 을 직접 출력 하면 된다.
c o d e code code

#include
#include
#include
#include
#include
using namespace std;
const int N=1e5*20;
struct node{
	int to,next,w;
}a[N*2];
struct gnode{
	int x,y,w,id;
}g[N],b[N];
int n,d,num,tot,cnt,rt0,rt1;
int ls[N],in[N],f[N],w[N];
int lson[N],rson[N],v1[N],v2[N];
bool vis[N];
queue<int> q;
void addl(int x,int y,int w){
	a[++tot].to=x;
	a[tot].next=ls[y];
	a[tot].w=w;ls[y]=tot;
}
void Build(int &x,int l,int r,int z){
	x=++num;
	if(l==r){
		if(z)addl(x,g[l].id,0);
		else addl(x,b[l].id,0);
		return;
	}
	int mid=(l+r)>>1;
	Build(lson[x],l,mid,z);
	Build(rson[x],mid+1,r,z);
	addl(x,lson[x],0);addl(x,rson[x],0);
	return;
}
void Change(int x,int L,int R,int l,int r,int pos){
	if(l>r)return;
	if(L==l&&R==r)
	{addl(pos,x,1);return;}
	int mid=(L+R)>>1;
	if(r<=mid)Change(lson[x],L,mid,l,r,pos);
	else if(l>mid)Change(rson[x],mid+1,R,l,r,pos);
	else Change(lson[x],L,mid,l,mid,pos),Change(rson[x],mid+1,R,mid+1,r,pos);
	return;
}
void SPFA(){
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=ls[x];i;i=a[i].next){
			int y=a[i].to;
			if(f[x]+a[i].w<f[y]){
				f[y]=f[x]+a[i].w;
				if(!vis[y]){
					q.push(y);
					vis[y]=1;
				}
			}
		}
		vis[x]=0;
	}
}
bool cmp1(gnode x,gnode y)
{return x.x<y.x;}
bool cmp2(gnode x,gnode y)
{return x.y<y.y;}
int main()
{
	scanf("%d%d",&n,&d);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&b[i].x,&b[i].y),b[i].id=i;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&g[i].x,&g[i].y),g[i].id=i+n;
	sort(b+1,b+1+n,cmp1);
	sort(g+1,g+1+n,cmp2);
	num=n*2;
	Build(rt0,1,n,0);
	Build(rt1,1,n,1);
	for(int i=1;i<=n;i++)v1[i]=b[i].x;
	for(int i=1;i<=n;i++)v2[i]=g[i].y;
	sort(b+1,b+1+n,cmp2);
	sort(g+1,g+1+n,cmp1);
	int link=1;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++){
		int l=lower_bound(v2+1,v2+1+n,b[i].y)-v2;
		int r=upper_bound(v2+1,v2+1+n,b[i].y+d)-v2-1;
		Change(rt1,1,n,l,r,b[i].id);
		if(!b[i].y)q.push(b[i].id),f[b[i].id]=0,vis[b[i].id]=1;
	}
	for(int i=1;i<=n;i++){
		int l=lower_bound(v1+1,v1+1+n,g[i].x)-v1;
		int r=upper_bound(v1+1,v1+1+n,g[i].x+d)-v1-1;
		Change(rt0,1,n,l,r,g[i].id);
		if(!g[i].x)q.push(g[i].id),f[g[i].id]=0,vis[g[i].id]=1;
	}
	SPFA();
	for(int i=1;i<=n;i++){
		if(f[i]>2147483647/3)printf("-1
");
		else printf("%d
",f[i]+1);
	}
}