[JOISC 2021 Day2] 道路の建設案 (Road Construction)
题意
给定图上 \(n\) 个点，求前 \(k\) 小曼哈顿距离点对距离。
题解
很好的一道题。
首先有一个 \(O(nlog^2n)\) 的做法，个人感觉还是很有启发性的。
一般对于第 \(k\) 小的处理方法是二分，二分第 \(k\) 小的距离是多少。
然后统计大于等于这个距离的点对数，注意到曼哈顿距离不太好满足，考虑转化为切比雪夫距离。
这样两维就分开了，考虑先将 \(x\) 超过距离的计算上，然后只对 \(x\) 不超过的计算 \(y\) 的贡献，容易发现这样可以用线段树维护。
但是每求一个都要二分，最坏的时间复杂度会达到 \(O(nklog^2n)\)，这样很不牛。
为什么不牛，因为我们只关注了点对的数量，无法具体的对应到点对上，但一般题这样做的原因是因为 \(k\) 比较大。
但是这题 \(k\) 和 \(n\) 是同阶的，我们可以发现我们其实可以暴力找到所有合法点对。
显然可以直接用 multiset 直接暴力数，很好做。
所以我们找到第 \(k\) 小的路径长度 \(mid\) 之后，再找一下小于等于 \(mid-1\) 的所有点对就好了，时间复杂度 \(O(nlog^2n)\)。
然后有一个 \(O(nlogn)\) 的做法，还是很牛的。
首先对于这种 \(k\) 比较小的问题，一般都是使用类似超级钢琴的做法。
对于每个点找到左边最近的点对，然后丢到堆里面，然后取出来之后扩展找第 \(2\) 小，第 \(3\) 小等。
考虑怎么找左边最近的点，一般的做法是扫描线，左边的点的 \(x\) 都是被减的，然后将 \(y\) 放到线段树上维护一个 \(y-x,-y-x\) 即可。
然后由于每一个点到后面都要找次小值，而且不能确定顺序，所以要可持久化扫描线上线段树的版本。
考虑如何找次小值，删除最小值即可，但是因为可持久化了，所以为了防止影响其它版本，所以仍然要新建版本。
为了好写可以将值的离散化成互不相同的值，因为在线段树上同一个叶节点维护的东西可能会比较麻烦，时间复杂度 \(O(nlogn)\)。
点击查看代码
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define rg register
#define pc putchar
#define gc getchar
#define pf printf
#define space pc(' ')
#define enter pc('\n')
#define me(x,y) memset(x,y,sizeof(x))
#define pb push_back
#define FOR(i,k,t,p) for(rg int i(k) ; i <= t ; i += p)
#define ROF(i,k,t,p) for(rg int i(k) ; i >= t ; i -= p)
using namespace std ;
bool s_gnd ;
inline void read(){}
template<typename T,typename ...T_>
inline void read(T &x,T_&...p)
{
x = 0 ;rg int f(0) ; rg char c(gc()) ;
while(!isdigit(c)) f |= (c=='-'),c = gc() ;
while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = gc() ;
x = (f?-x:x) ;
read(p...);
}
int stk[30],tp ;
inline void print(){}
template<typename T,typename ...T_>
inline void print(T x,T_...p)
{
if(x < 0) pc('-'),x = -x ;
do stk[++tp] = x%10,x /= 10 ; while(x) ;
while(tp) pc(stk[tp--]^48) ; space ;
print(p...) ;
}
bool S_GND ;
const int N = 5e5+5 ;
const int INF = 1e18+7 ;
int n,k,top ;
pii b[N] ;
int rt[N] ;
unordered_map<int,int>rk ;
struct Node{int x,y ;}a[N] ;
struct RP{int x,y,id ;}c[N] ;
struct Pair
{
int u,v,w ;
bool operator < (const Pair &A) const
{
return w > A.w ;
}
} ;
priority_queue<Pair>q ;
int cmp(RP x,RP y) {return x.x < y.x ;}
struct Seg{int l,r ; pii mx,mi ;}tr[N*60] ;
#define ls(x) tr[x].l
#define rs(x) tr[x].r
#define mi(x) tr[x].mi
#define mx(x) tr[x].mx
#define mid (le+ri>>1)
void update(int x)
{
mx(x) = max(mx(ls(x)),mx(rs(x))) ;
mi(x) = min(mi(ls(x)),mi(rs(x))) ;
}
void Build(int &x,int le = 1,int ri = n)
{
x = ++top ; if(le == ri) {mi(x) = {INF,0},mx(x) = {-INF,0} ; return ;}
Build(ls(x),le,mid),Build(rs(x),mid+1,ri),update(x) ;
}
void Insert(int &x,int y,int k,int xi,int yi,int id,int le = 1,int ri = n)
{
x = ++top,tr[x] = tr[y] ; if(le == ri) {mx(x) = {xi+yi,id},mi(x) = {yi-xi,id} ; return ;}
(k <= mid) ? Insert(ls(x),ls(y),k,xi,yi,id,le,mid) : Insert(rs(x),rs(y),k,xi,yi,id,mid+1,ri) ; update(x) ;
}
void Delete(int &x,int y,int k,int le = 1,int ri = n)
{
x = ++top,tr[x] = tr[y] ; if(le == ri) {mx(x) = {-INF,0},mi(x) = {INF,0} ; return ;}
(k <= mid) ? Delete(ls(x),ls(y),k,le,mid) : Delete(rs(x),rs(y),k,mid+1,ri) ; update(x) ;
}
pii Query_mi(int x,int L,int R,int le = 1,int ri = n)
{
if(le >= L && ri <= R) return mi(x) ; pii res = {INF,0} ;
if(L <= mid) res = Query_mi(ls(x),L,R,le,mid) ; if(mid < R) res = min(res,Query_mi(rs(x),L,R,mid+1,ri)) ; return res ;
}
pii Query_mx(int x,int L,int R,int le = 1,int ri = n)
{
if(le >= L && ri <= R) return mx(x) ; pii res = {-INF,0} ;
if(L <= mid) res = Query_mx(ls(x),L,R,le,mid) ; if(mid < R) res = max(res,Query_mx(rs(x),L,R,mid+1,ri)) ; return res ;
}
signed main()
{
//cerr<<(double)(&s_gnd-&S_GND)/1024.0/1024.0 ;
// freopen(".in","r",stdin) ;
// freopen(".out","w",stdout) ;
read(n,k) ;
FOR(i,1,n,1) read(a[i].x,a[i].y),c[i].id = i ;
FOR(i,1,n,1) b[i] = {a[i].x,i} ; sort(b+1,b+1+n) ;
FOR(i,1,n,1) c[b[i].second].x = i ;
FOR(i,1,n,1) b[i] = {a[i].y,i} ; sort(b+1,b+1+n) ;
FOR(i,1,n,1) c[b[i].second].y = i ;
sort(c+1,c+1+n,cmp),Build(rt[0],1,n) ; // cerr<<"!" ;
// FOR(i,1,n,1) print(c[i].id) ; enter ;
FOR(i,1,n,1)
{
pii jd = {INF,INF} ;
pii pos = Query_mx(rt[i-1],1,c[i].y) ;
if(pos.second) jd = min(jd,{a[c[i].id].x+a[c[i].id].y-pos.first,pos.second}) ; //print(a[c[i].id].x+a[c[i].id].y-pos.first,pos.first,pos.second),enter ;
pos = Query_mi(rt[i-1],c[i].y,n) ;
if(pos.second) jd = min(jd,{a[c[i].id].x+pos.first-a[c[i].id].y,pos.second}) ; //print(a[c[i].id].x+pos.first-a[c[i].id].y,pos.first,pos.second),enter ;
if(jd.second) q.push({jd.second,i,jd.first}) ; Insert(rt[i],rt[i-1],c[i].y,a[c[i].id].x,a[c[i].id].y,i) ;
}
FOR(p,1,k,1)
{
auto [x,y,w] = q.top() ; q.pop() ;
print(w),enter ; Delete(rt[y-1],rt[y-1],c[x].y) ; int i = y ;
pii jd = {INF,INF},pos = Query_mx(rt[i-1],1,c[i].y) ;
if(pos.second) jd = min(jd,{a[c[i].id].x+a[c[i].id].y-pos.first,pos.second}) ;
pos = Query_mi(rt[i-1],c[i].y,n) ;
if(pos.second) jd = min(jd,{a[c[i].id].x+pos.first-a[c[i].id].y,pos.second}) ;
if(jd.second) q.push({jd.second,i,jd.first}) ;
}
return 0 ;
}