【 NOI 2019 】 【 LOJ 3259 】 【 낙 곡 P5471 】 점프 (K - D Tree) (최 단 로)

LOJ 전송 문
낙 곡 전송 문
사설:
나 는 이것 이 난 장 판 이 라 고 생각한다. 그러나 복잡 도가 우수한 난 장 판 이다. 마치 O (m log ⁡ m + n log ⁡ 2 n) O (m \ log m + n \ log ^ 2 n) O (mlogm + nlog2n) 만 있 는 것 같다.
KDTree 최적화 그림 을 보고 dijkstra 를 달리 고 스크롤 절단 정적 KD - tree 를 썼 습 니 다. 변 수 는 88pts 에 불과 합 니 다.
그래서 우리 의 전략 은 변경 을 만 들 지 않 는 것 이다.우선 대기 열 에 전체 사각형 을 유지 한 다음 에 특정한 데이터 구조 로 현재 사각형 내부 에 접근 하지 않 은 모든 점 을 물 어 보 는 것 을 고려 합 니 다.
직접 KD - tree 에 오 르 는 것 은 기대 O (n 3 2) O (n ^ {\ frac {3} {2}}) O (n23) 입 니 다. 그러나 이 KD - tree 는 정적 인 것 을 발 견 했 습 니 다. 그래서 스크롤 절단 을 고려 하여 차원 에 따라 스크롤 한 다음 에 욕심 을 내 서 나 무 를 만 드 는 것 은 O (n log * 8289) O (n \ log ^ 2n) O (nlog2n) 만 있 고 상수 가 매우 작 습 니 다.
그리고 우선 순위 에서 사각형 을 꺼 내 서 KD - tree 에서 찾 으 면 됩 니 다. 이 부분의 전체 복잡 도 는 O (n log ⁡ n) O (n \ log n) O (nlogn) 이 고 상수 가 44 를 초과 하지 않 습 니 다.
게다가 dijkstra 의 복잡 도 는 O (m log * 8289 ° m + n log * 8289 ° 2 n) O (m \ log m + n \ log ^ 2 n) O (mlogm + nlog2n) 입 니 다.
LOJ 와 로 곡 스피드 랭 킹 Rk 1 을 따 냈 다.
Update：
왜 자꾸 내 가 복잡 하 게 휴가 를 보 냈 다 고 하 는 거 야?
잘 보 세 요. 이것 은 어떤 전통 적 인 KD - tree 트 리 방식 도 아 닙 니 다!
증명 해 보 세 요:
건축 수: 욕심 에 따라 (내 가 어떻게 구분 하 는 지 직접 보고) 좌우 아들 의 포 인 트 를 엄 격 히 아버지 포인트 의 절반 으로 하고, 한 노드 의 건축 수 는 가로 세로 좌표 에 따라 f (n) = O (n log ⁡ n) f (n) = O (n \ log n) f (n) = O (n) = O (nlogn), 복잡 도 병목 은 바로 여기에 있다. 건축 수 총 복잡 도 T (n) = 2T (n 2) + f (n) = O (n log ⁡ 2 n) T (n) = 2T(\frac{n}{2})+f(n)=O(n\log^2n) T(n)=2T(2n​)+f(n)=O(nlog2n)
조회: 우선 트 리 높이 는 O (log ⁡ n) O (\ log n) O (logn) 이 고, 빈 사각형 의 접근 복잡 도 는 O (log ⁡ n) O (\ log n) O (logn) O (logn) 만 있 습 니 다.
분명 한 것 은 이 문 제 는 한 잎 노드 를 방문 한 후에 삭제 해 야 하기 때문에 적어도 뿌리 까지 가 는 경로 의 점 인 s i z - 1 siz - 1 siz - 1 siz - 1 이다. 빈 노드 는 다시 방문 하지 않 아 도 복잡 도 는 O (＞ s i z) O (\ sum siz) O (＞ siz) 이 고 나 무 는 O (log ⁡ n) O (\ log n) O (logn) O (logn) 이 며 한 잎 은 O (log ⁡ n) O (\ log n) O (logn) 에 만 있 을 것 이다.개 노드 에 공헌 이 있 기 때문에 총 복잡 도 는 O (∑ s i z) = O (n log ⁡ n) O (\ sum siz) = O (n \ log n) O (∑ siz) = O (nlogn) 이 고 굳이 빈 사각형 으로 카드 를 끊 으 려 면 O (m log ⁡ n) O (m \ log n) O (mlogn) O (mlogn) 이다.
복잡 도와 상수 가 모두 매우 우수 하 다.
코드:

#include
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<22|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	template<typename T>
	inline T get(){
		char c;
		while(!isdigit(c=gc()));T num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
	inline int getint(){return get<int>();}
}
using namespace IO;

using std::cerr;
using std::cout;
typedef std::pair<ll,int> pli;
#define fi first
#define se second

cs int N=7e4+4,M=1.5e5+5;

int n,m,w,h;

struct Point{
	int x,y,id;
}p[N];

int nd[N],cnt;
namespace KDT{
	cs int N=::N<<1;
	int lc[N],rc[N],typ[N],now,rt;
	int U[N],D[N],L[N],R[N],siz[N],id[N];
	
	bool cmp1(cs Point &a,cs Point &b){return a.x<b.x;}
	bool cmp2(cs Point &a,cs Point &b){return a.y<b.y;}
	
	void build(int &rt,int l,int r,int u,int d,int pl,int pr,int lasttyp=0){
		rt=++now;
		L[rt]=l,R[rt]=r,D[rt]=d,U[rt]=u;
		siz[rt]=pr-pl+1;
		if(pl==pr){
			id[rt]=p[pl].id;
			return ;
		}
		if(u==d){
			typ[u]=1;
			if(typ[u]!=lasttyp)std::sort(p+pl,p+pr+1,cmp1);
			int mid=pl+pr>>1;
			build(lc[rt],l,p[mid].x,u,u,pl,mid,1);
			build(rc[rt],p[mid+1].x,r,u,u,mid+1,pr,1);
			return ;
		}
		if(l==r){
			typ[u]=2;
			if(typ[u]!=lasttyp)std::sort(p+pl,p+pr+1,cmp2);
			int mid=pl+pr>>1;
			build(lc[rt],l,l,u,p[mid].y,pl,mid,2);
			build(rc[rt],l,l,p[mid+1].y,d,mid+1,pr,2);
			return ;
		}
		typ[u]=3-lasttyp;
		if(typ[u]==3)typ[u]=1;
		if(typ[u]==1){
			std::sort(p+pl,p+pr+1,cmp1);
			int mid=pl+pr>>1;
			int nu=0x3f3f3f3f,nd=0;
			for(int re i=pl;i<=mid;++i)nu=std::min(nu,p[i].y),nd=std::max(nd,p[i].y);
			build(lc[rt],l,p[mid].x,nu,nd,pl,mid,1);
			nu=0x3f3f3f3f,nd=0;
			for(int re i=mid+1;i<=pr;++i)nu=std::min(nu,p[i].y),nd=std::max(nd,p[i].y);
			build(rc[rt],p[mid+1].x,r,nu,nd,mid+1,pr,1);
		}
		else {
			std::sort(p+pl,p+pr+1,cmp2);
			int mid=pl+pr>>1;
			int nl=0x3f3f3f3f,nr=0;
			for(int re i=pl;i<=mid;++i)nl=std::min(nl,p[i].x),nr=std::max(nr,p[i].x);
			build(lc[rt],nl,nr,u,p[mid].y,pl,mid,2);
			nl=0x3f3f3f3f,nr=0;
			for(int re i=mid+1;i<=pr;++i)nl=std::min(nl,p[i].x),nr=std::max(nr,p[i].x);
			build(rc[rt],nl,nr,p[mid+1].y,d,mid+1,pr,2);
		}
	}
	
	void get(int rt,int l,int r,int u,int d){
		if(!siz[rt])return ;
		if(r<L[rt]||R[rt]<l||d<U[rt]||D[rt]<u)return ;
		if(id[rt]){
			siz[rt]=0;
			nd[++cnt]=id[rt];
			return ;
		}
		if(typ[rt]==1){
			if(l<=R[lc[rt]])get(lc[rt],l,r,u,d);
			if(L[rc[rt]]<=r)get(rc[rt],l,r,u,d);
		}
		else {
			if(u<=D[lc[rt]])get(lc[rt],l,r,u,d);
			if(U[rc[rt]]<=d)get(rc[rt],l,r,u,d);
		}
		siz[rt]=siz[lc[rt]]+siz[rc[rt]];
	}
}

struct rac{
	int l,r,u,d;ll t;
	rac(int _l,int _r,int _u,int _d,ll _t):l(_l),r(_r),u(_u),d(_d),t(_t){}
	friend bool operator>(cs rac &a,cs rac &b){
		return a.t>b.t;
	}
};

std::vector<rac> G[N];
std::priority_queue<rac,std::vector<rac>,std::greater<rac> > q;

bool vis[N];
ll dist[N];

inline void Dij(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(rac &t:G[1])q.push(t);
	vis[1]=true;
	while(!q.empty()){
		int l=q.top().l,r=q.top().r,u=q.top().u,d=q.top().d;ll t=q.top().t;
		q.pop();cnt=0;
		KDT::get(KDT::rt,l,r,u,d);
		for(int re i=1;i<=cnt;++i){
			int u=nd[i];if(vis[u])continue;vis[u]=true;
			dist[u]=t;
			for(rac &e:G[u]){
				q.push(rac(e.l,e.r,e.u,e.d,e.t+t));
			}
		}
	}
}

int mnx=0x3f3f3f3f,mxx,mny=0x3f3f3f3f,mxy;
signed main(){
//	freopen("jump.in","r",stdin);freopen("jump.out","w",stdout);
	n=getint(),m=getint(),w=getint(),h=getint();
	for(int re i=1;i<=n;++i){
		p[i].x=getint(),p[i].y=getint(),p[i].id=i;
		mnx=std::min(mnx,p[i].x);
		mxx=std::max(mxx,p[i].x);
		mny=std::min(mny,p[i].y);
		mxy=std::max(mxy,p[i].y);
	}
	KDT::build(KDT::rt,mnx,mxx,mny,mxy,1,n);
	for(int re i=1;i<=m;++i){
		int u=getint(),w=getint(),L=getint(),R=getint(),U=getint(),D=getint();
		G[u].push_back(rac(L,R,U,D,w));
	}
	Dij();
	for(int re i=2;i<=n;++i)cout<<dist[i]<<"
";
	return 0;
}