题意

在平面直角坐标系中找出所有\(dist(i, j) \leq k\)的点对个数\(\leq 4\times 10^5\)

\(1 \le n \le 2\times 10^5\)
\(1 \le k \le 1.5\times 10^5\)

hint

分块

不是ds

sol

考虑将网格分割，每\(k\)行\(k\)列分一格。注意到分完块以后对于一个点\((i, j)\)所在的块\(B_{(i, j)}\)，和他距离\(\leq k\)的点必然会在这个块的四周(\(|dx|, |dy| \le 1\))。然后直接做发现常数非常的小，再加持上atcoder的机子就随便过了。复杂度不是很清楚是不是正确的。

code

贴出核心代码， 完整代码在Atcoder submission

  auto dist = [&](int i, int j) {
    return sqr(p[i].first - p[j].first) + sqr(p[i].second - p[j].second);
  };
  rep(i, 1, n) Mp[mkp(p[i].first / k, p[i].second / k)].eb(i);
  vector<pair<ll, ll> > ans;
  for (auto [pos, v] : Mp) {
    auto [x, y] = pos;
    rep(d, 0, 8) {
      int tx = x + dx[d], ty = y + dy[d];
      if (!Mp.count(mkp(tx, ty))) continue;
      for (auto i : Mp[pos])
        for (auto j : Mp[mkp(tx, ty)])
          if (i < j && dist(i, j) <= sqr(k)) ans.eb(i, j);
    }
  }