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 ? 2 n ) O(n\log^2n) O(nlog2n)，而且常数极小。
【KD-Tree|【NOI2019】【LOJ3259】【洛谷P5471】弹跳（K-D Tree）（最短路）】然后我们从优先队列里面拿出来矩形，在KD-Tree上面找就行了，这部分找点的总复杂度为 O ( n log ? n ) O(n\log n) O(nlogn)，常数不超过 4 4 4。
加上dijkstra的复杂度也才 O ( m log ? m + n log ? 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(nlogn)，复杂度瓶颈就在这里，建树总复杂度 T ( n ) = 2 T ( 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)
显然这道题由于是访问一个叶子节点之后需要删除，至少会导致其到根的路径上的点的 s i z ? 1 siz-1 siz?1。空节点不用再次访问，则复杂度显然为 O ( ∑ s i z ) O(\sum siz) O(∑siz)，而树高为 O ( log ? n ) O(\log n) 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)。
复杂度和常数都十分优秀。
代码：

#include #define ll long long #define re register #define gc get_char #define cs constnamespace 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 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(); } } using namespace IO; using std::cerr; using std::cout; typedef std::pair pli; #define fi first #define se secondcs 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>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(cs rac &a,cs rac &b){ return a.t>b.t; } }; std::vector G[N]; std::priority_queue,std::greater > 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<