問題
$N$ 個の点 $(x_i, y_i)$ に対し、点の移動クエリと矩形内点カウントクエリを処理せよ（$0 \le x, y \le 10^9$）。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $1 \le N \le 10^5$ |
| $Q$ | $1 \le Q \le 10^5$ |
| $x_i, y_i$ | $0 \le x_i, y_i \le 10^9$ |
入出力例
入力例 1
5 4
1 3
4 2
6 5
2 8
7 1
2 1 7 1 5
1 3 1 0
2 1 7 1 5
2 5 9 1 9出力例 1
3
2
2初期: (1,3),(4,2),(6,5),(2,8),(7,1)。矩形[1,7]×[1,5]に(1,3),(4,2),(6,5)の3点。点3を(7,5)に移動。再クエリ: (1,3),(4,2),(7,5)で3点→[1,7]×[1,5]内は(1,3),(4,2)で2点。
概念図: 2D BIT と包除原理
ヒント（段階的開示）
ヒント1: 方向性
点の更新（移動）を「削除 + 挿入」として扱う。動的な点集合への矩形カウントは座標圧縮 + 2D BIT で $O(\log^2 N)$ で処理できる。座標が大きいのでオフラインで全クエリを先読みする。
ヒント2: アプローチ
- 全クエリを先読みして発生しうる全 x, y 座標を収集
- x, y を独立に圧縮（座標数 ≤ N+Q）
- 2D BIT で点追加/削除、矩形クエリに包除原理を適用
- 点移動 = 旧座標を -1、新座標を +1 で更新
ヒント3: コード骨格
# オフライン座標圧縮
all_x = {p[0] for p in pts}
all_y = {p[1] for p in pts}
# クエリで追加される座標も収集
for q in queries:
if q[0] == 1: ... # 移動後座標を収集
all_x = sorted(all_x); all_y = sorted(all_y)
x_idx = {v: i+1 for i, v in enumerate(all_x)}
y_idx = {v: i+1 for i, v in enumerate(all_y)}
# 2D BIT update/query
# 矩形 [xl,xr]x[yl,yr] = query(xr,yr)-query(xl-1,yr)-query(xr,yl-1)+query(xl-1,yl-1)模範解答 (Python)
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
def solve():
N, Q = map(int, input().split())
pts = []
for _ in range(N):
x, y = map(int, input().split())
pts.append([x, y])
queries = []
for _ in range(Q):
line = list(map(int, input().split()))
queries.append(line)
# オフライン: 全座標を収集
all_x_set = set()
all_y_set = set()
for p in pts:
all_x_set.add(p[0])
all_y_set.add(p[1])
cur = [p[:] for p in pts]
for q in queries:
if q[0] == 1:
i, dx, dy = q[1]-1, q[2], q[3]
cur[i][0] += dx
cur[i][1] += dy
all_x_set.add(cur[i][0])
all_y_set.add(cur[i][1])
else:
_, xl, xr, yl, yr = q
all_x_set.update([xl, xr])
all_y_set.update([yl, yr])
all_x = sorted(all_x_set)
all_y = sorted(all_y_set)
X = len(all_x)
Y = len(all_y)
bit = [[0] * (Y + 1) for _ in range(X + 1)]
def update(xi, yi, delta):
i = xi
while i <= X:
j = yi
while j <= Y:
bit[i][j] += delta
j += j & (-j)
i += i & (-i)
def query(xi, yi):
s = 0
i = xi
while i > 0:
j = yi
while j > 0:
s += bit[i][j]
j -= j & (-j)
i -= i & (-i)
return s
def rect_query(xl, xr, yl, yr):
xi_l = bisect_left(all_x, xl) + 1
xi_r = bisect_right(all_x, xr)
yi_l = bisect_left(all_y, yl) + 1
yi_r = bisect_right(all_y, yr)
if xi_l > xi_r or yi_l > yi_r:
return 0
return (query(xi_r, yi_r)
- query(xi_l - 1, yi_r)
- query(xi_r, yi_l - 1)
+ query(xi_l - 1, yi_l - 1))
# 初期点を挿入
state = [p[:] for p in pts]
for p in state:
xi = bisect_left(all_x, p[0]) + 1
yi = bisect_left(all_y, p[1]) + 1
update(xi, yi, 1)
out = []
for q in queries:
if q[0] == 1:
idx, dx, dy = q[1]-1, q[2], q[3]
ox, oy = state[idx]
update(bisect_left(all_x, ox)+1, bisect_left(all_y, oy)+1, -1)
state[idx][0] += dx
state[idx][1] += dy
nx, ny = state[idx]
update(bisect_left(all_x, nx)+1, bisect_left(all_y, ny)+1, 1)
else:
_, xl, xr, yl, yr = q
out.append(rect_query(xl, xr, yl, yr))
print('\n'.join(map(str, out)))
solve()Step-by-Step 解説
Step 1: オフライン座標圧縮
更新クエリで発生する新座標を先読みして収集。x, y 座標を独立にソートし、1-indexed のインデックスに変換する。
Step 2: 2次元BITの構造
BIT を2次元に拡張。外側のループが x 軸、内側が y 軸。1回の更新/クエリで $O(\log X \cdot \log Y)$。
Step 3: 矩形クエリの包除原理
$[xl, xr] \times [yl, yr]$ の点数 = $\text{BIT}(xr, yr) - \text{BIT}(xl-1, yr) - \text{BIT}(xr, yl-1) + \text{BIT}(xl-1, yl-1)$
Step 4: 点移動の実装
旧座標に $-1$、新座標に $+1$ を更新することで論理的な「移動」を実現。削除と挿入を分離して実装。
Step 5: 計算量
| 操作 | 計算量 |
|---|---|
| 座標圧縮 | $O((N+Q) \log (N+Q))$ |
| 初期挿入 | $O(N \log^2 N)$ |
| 各クエリ | $O(\log^2 (N+Q))$ |
| 全体 | $O((N+Q) \log^2 (N+Q))$ |
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 更新後座標の収集漏れ | 移動先の座標を全クエリ先読みしない | 全クエリを先読みして all_x/y に追加 |
| bisect の使い分け | 境界の包含/除外を間違える | 右端は bisect_right、左端は bisect_left+1 |
| 1-indexed vs 0-indexed | BITは1-indexed が必須 | bisect_left の結果に +1 |
| 移動順序のミス | 削除前に新座標を state に書き込む | 旧座標を削除してから state を更新 |
次のステップ
発展問題: オンラインでの矩形カウント（動的マージソートツリー、KD-Tree）。または3次元空間での直方体カウント（3D BIT）。