rt

check 时为什么用线段树做扫描线会比用 set 判断慢这么多？

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lp(i, j, n) for(int i = j; i <= n; ++i)
#define dlp(i, n, j) for(int i = n; i >= j; --i)
#define mst(n, v) memset(n, v, sizeof(n))
#define mcy(n, v) memcpy(n, v, sizeof(v))
#define INF 1e18
#define MAX4 0x3f3f3f3f
#define MAX8 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define pll pair<ll, ll>
#define co(x) cerr << (x) << ' '
#define cod(x) cerr << (x) << endl
#define fi first
#define se second
#define eps 1e-8
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 ^ 1)
#define ls ch[x][0]
#define rs ch[x][1]
#define pb(x) emplace_back(x)

using namespace std;

const int N = 250010;
const ll V1 = -2e9, V2 = 2e9;

struct node {
	ll x, y;
	
	bool operator < (const node & t) const { return x == t.x? y < t.y : x < t.x; }
} nd[N];

int n, K;

namespace Sg {
	const int S = 60000000;
	
	int cnt[S], lc[S], rc[S], tot, rt;
	
	void pu(int x) { cnt[x] = cnt[lc[x]] + cnt[rc[x]]; }
	
	void mdf(int & x, ll l, ll r, int p, int v) {
		if(!x) x = ++tot, cnt[x] = lc[x] = rc[x] = 0;
		if(l == r) return cnt[x] += v, void();
		ll mid = l + r >> 1;
		p <= mid? mdf(lc[x], l, mid, p, v) : mdf(rc[x], mid + 1, r, p, v), pu(x);
	}
	
	int qry(int x, ll l, ll r, ll ql, ll qr) {
		if(ql > qr) return 0;
		if(!x) return 0;
		if(ql <= l && qr >= r) return cnt[x];
		ll mid = l + r >> 1, res = 0;
		if(ql <= mid) res = qry(lc[x], l, mid, ql, qr);
		if(qr > mid) res += qry(rc[x], mid + 1, r, ql, qr);
		return res;
	}
} using namespace Sg;

bool chk(ll dst) {
	rt = tot = 0;
	int p = 1, cnt = 0;
	lp(i, 1, n) {
		while(p < i && nd[i].x - nd[p].x > dst) mdf(rt, V1, V2, nd[p].y, -1), ++p;
		cnt += qry(rt, V1, V2, max(V1, nd[i].y - dst), min(V2, nd[i].y + dst));
		if(cnt >= K) return true;
		mdf(rt, V1, V2, nd[i].y, 1);
	}
	return cnt >= K;
}

set<node> s;
ll ans[N]; int m;

signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
#ifndef READ
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
	cin >> n >> K;
	int x, y;
	lp(i, 1, n) cin >> x >> y, nd[i].x = x + y, nd[i].y = x - y;
	sort(nd + 1, nd + 1 + n);
	ll l = 0, r = 4e9;
	while(l < r) {
		ll mid = l + r >> 1;
		if(chk(mid)) r = mid;
		else l = mid + 1;
	}
	int p = 1;
	lp(i, 1, n) {
		while(p < i && nd[i].x - nd[p].x > l - 1) s.erase({nd[p].y, nd[p].x}), ++p;
		for(auto it = s.lower_bound({nd[i].y - (l - 1), V1}); it != s.end() && it->x - nd[i].y <= (l - 1); ++it) {
			ans[++m] = max(nd[i].x - it->y, abs(nd[i].y - it->x));
		}
		s.insert({nd[i].y, nd[i].x});
	}
	sort(ans + 1, ans + 1 + m);
	lp(i, 1, K) cout << (i <= m? ans[i] : l) << endl;
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lp(i, j, n) for(int i = j; i <= n; ++i)
#define dlp(i, n, j) for(int i = n; i >= j; --i)
#define mst(n, v) memset(n, v, sizeof(n))
#define mcy(n, v) memcpy(n, v, sizeof(v))
#define INF 1e18
#define MAX4 0x3f3f3f3f
#define MAX8 0x3f3f3f3f3f3f3f3f
#define pii pair<int, int>
#define pll pair<ll, ll>
#define co(x) cerr << (x) << ' '
#define cod(x) cerr << (x) << endl
#define fi first
#define se second
#define eps 1e-8
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 ^ 1)
#define ls ch[x][0]
#define rs ch[x][1]
#define pb(x) emplace_back(x)

using namespace std;

const int N = 250010;
const ll V1 = -2e9, V2 = 2e9;

struct node {
	ll x, y;
	
	bool operator < (const node & t) const { return x == t.x? y < t.y : x < t.x; }
} nd[N];

int n, K;

set<node> s;
ll ans[N]; int m;
bool chk(ll dst) {
	int p = 1;
	s.clear(), m = 0;
	lp(i, 1, n) {
		while(p < i && nd[i].x - nd[p].x > dst) s.erase({nd[p].y, nd[p].x}), ++p;
		for(auto it = s.lower_bound({nd[i].y - dst, V1}); it != s.end() && it->x - nd[i].y <= dst; ++it) {
			ans[++m] = max(nd[i].x - it->y, abs(nd[i].y - it->x));
			if(m >= K) return true;
		}
		s.insert({nd[i].y, nd[i].x});
	}
	return m >= K;
}

signed main() {
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
#ifndef READ
    ios::sync_with_stdio(false);
    cin.tie(0);
#endif
	cin >> n >> K;
	int x, y;
	lp(i, 1, n) cin >> x >> y, nd[i].x = x + y, nd[i].y = x - y;
	sort(nd + 1, nd + 1 + n);
	ll l = 1, r = 4e9;
	while(l < r) {
		ll mid = l + r >> 1;
		if(chk(mid)) r = mid;
		else l = mid + 1;
	}
	chk(l - 1);
	sort(ans + 1, ans + 1 + m);
	lp(i, 1, K) cout << (i <= m? ans[i] : l) << endl;
    return 0;
}

上面是线段树，下面是 set，一个 10.22s，一个 1.11s。