个人排位赛10补题记录

Manhattan Distance (Gym 102569C)

题目大意：给定$n$个点$(x_i,y_i)$，将所有不同点对（共$\frac{n(n-1)}{2}$个点对）的曼哈顿距离排序，求第$k$大的距离。（$2\le n \le 100000$）

解法：

某个点$u$与点$v$的曼哈顿距离小于$d$，则$u$在以$v$中心的一个旋转了$45$度的正方形内，该正方形的顶点为$(x+d,y),(x-d,y),(x,y+d),(x,y-d)$。

可以将坐标系逆时针旋转$45$度，并放大$\sqrt{2}$倍，则新坐标系上的点为$(x+y,y-x)$。若点$u'$与点$v'$在原坐标系中曼哈顿距离小于$d$，则点$u'$在以$(x_{v'}-d,y_{v'}-d),(x_{v'}+d,y_{v'}-d),(x_{v'}-d,y_{v'}+d),(x_{v'}+d,y_{v'}+d)$为顶点的正方形内。

二分查找时用双指针+树状数组优化即可。

#include <bits/stdc++.h>
#define ll long long
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define pii pair<int, int>
using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 1000;

int unq[maxn], bit[maxn], unq_size;
ll n, k;
pii pts[maxn];

void modify(int pos, int v){
    while(pos <= unq_size){
        bit[pos] += v;
        pos += (-pos) & pos;
    }
}

int query(int pos){
    int ret = 0;
    while(pos > 0){
        ret += bit[pos];
        pos -= (-pos) & pos;
    }
    return ret;
}

ll check(int d){
    ll cnt = 0;
    memset(bit, 0, sizeof bit);
    for(int i=0, j = 0; i<n; i++){
        while(j < i && pts[i].first - pts[j].first > d){
            modify(lower_bound(unq + 1, unq + 1 + unq_size, pts[j].second) - unq, -1);
            j++;
        }
        cnt += query(upper_bound(unq + 1, unq + 1 + unq_size, pts[i].second + d) - unq - 1);
        cnt -= query(lower_bound(unq + 1, unq + 1 + unq_size, pts[i].second - d) - unq - 1);
        modify(lower_bound(unq + 1, unq + 1 + unq_size, pts[i].second) - unq, 1);
    }
    return cnt;
}

void solve(){
    cin >> n >> k;
    for(int i=0, x, y; i<n; i++){
        cin >> x >> y;
        pts[i].first = x + y;
        pts[i].second = y - x;
        unq[++unq_size] = pts[i].second;
    }
    sort(unq + 1, unq + 1 + unq_size);
    unq_size = unique(unq + 1, unq + 1 + unq_size) - unq - 1;

    sort(pts, pts + n);

    int l = 0, r = 4e8 + 1, ans = 0, mid;
    while(l <= r){
        mid = (l + r) >> 1;
        ll tmp = check(mid);
        if(tmp >= k){
            ans = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << ans << '\n';
}
  
signed main(){
    Android;
    solve();
}