给定平面上 (n) 个圆 ((x_i,y_i,r_i))。每次操作选择最大的圆中编号最小的，将所有与其有交的圆删掉，直到没有剩下的圆。
对每个圆，分别求其被哪个圆删掉。
(nle 3cdot 10^5,|x_i|,|y_i|,r_ile 10^9)。
首先有一个 sd 做法：把所有点随机旋转一个角度，然后跑 kdt。
然后有一个官方题解做法：设当前在考虑 ((x,y,r))，将无限平面分割成每格 (R imes R) 的网格，其中 (Rge r)，只需要考虑以其所在格为中心的 (5 imes 5) 的网格里的点。
而对于每个圆，检查它而不删掉它的次数仅有常数次，因为检查它的圆都比它大，而且相交的圆至多只有一个能检查它。
但是不能重构太多次，于是考虑倍增，仅当 (rle frac R2) 时才重构。
使用 hash 表维护每个块内的点，时间复杂度 (O(nlog V))，带一个不会算常数的 (O(n))。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N = 300003, V = 1500007, INF = 1e9;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0; bool f = false;
for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
} int n, cnt, R = 2e9, p[N], stk[N], tp, head[V], val[N], nxt[N], ans[N];
ULL _ = chrono::steady_clock::now().time_since_epoch().count();
struct Circ {
int x, y, r;
} c[N];
int Hah(int x, int y){return (((ULL)x<<32|y)^_) % V;}
void build(){
while(tp){head[stk[--tp]] = 0;} cnt = 0;
for(int i = 1;i <= n;++ i) if(!ans[i]){
int h = Hah((c[i].x + INF) / R, (c[i].y + INF) / R);
val[++cnt] = i; nxt[cnt] = head[h]; head[h] = cnt; stk[tp++] = h;
}
} bool check(int a, int b){
LL x = c[a].x - c[b].x, y = c[a].y - c[b].y, r = c[a].r + c[b].r;
return x * x + y * y <= r * r;
}
int main(){ read(n);
for(int i = 1;i <= n;++ i){
p[i] = i; read(c[i].x); read(c[i].y); read(c[i].r);
} stable_sort(p + 1, p + n + 1, [&](int x, int y){return c[x].r > c[y].r;});
for(int i = 1;i <= n;++ i){
int u = p[i]; if(ans[u]) continue;
if(c[u].r <= (R>>1)){R = c[u].r; build();}
int px = (c[u].x + INF) / R, py = (c[u].y + INF) / R;
for(int x = px-2;x <= px+2;++ x)
for(int y = py-2;y <= py+2;++ y){
int h = Hah(x, y);
for(int j = head[h], lst = 0;j;j = nxt[j]){
int v = val[j];
if(check(u, v)){ans[v] = u; if(lst) nxt[lst] = nxt[j]; else head[h] = nxt[j];}
else lst = j;
}
}
} for(int i = 1;i <= n;++ i) printf("%d%c", ans[i], "
"[i==n]);
}