Day 063-Q5 | オンライン平面点追加・矩形カウント（Merge Sort Tree）

問題

2次元平面上での以下のオンラインクエリを処理せよ：

add x y: 点 $(x, y)$ を追加する
count x1 y1 x2 y2: 矩形 $[x_1, x_2] \times [y_1, y_2]$ 内の点の個数を出力する

制約

パラメータ	範囲
$Q$	$1 \le Q \le 10^5$
$x, y$	$0 \le x, y \le 10^9$
クエリ	オンライン（前の答えを使って座標が決まる可能性あり）

入出力例

入力例 1

7
add 1 2
add 3 4
add 2 1
count 1 1 3 3
add 5 5
count 2 2 6 6
count 0 0 10 10

出力例 1

3
2
5

count 1 1 3 3: 点(1,2),(3,4),(2,1) → 全3点が範囲内。count 2 2 6 6: (3,4),(5,5) の2点。count 0 0 10 10: 全5点。

概念図: 動的 Merge Sort Tree の構造

ヒント（段階的開示）

ヒント1: 方向性

オンライン 2D 点追加・矩形カウントは難しい問題。オフラインなら座標圧縮 + BIT で $O(N\log N)$。オンラインでは動的セグメント木 + 各ノードに y 座標のソート済みリスト（Merge Sort Tree）が定番。add と count ともに $O(\log^2 N)$。

ヒント2: アプローチ

x 軸を動的セグメント木（辞書ベース）で管理
各ノードに y 座標のソート済みリストを持つ
add(x, y): x に対応する $O(\log N)$ ノードに bisect.insort で y を挿入
count(x1,y1,x2,y2): x 軸の $[x_1,x_2]$ をカバーするノードで bisect による y カウント

ヒント3: コード骨格

import bisect
from collections import defaultdict

class DynMergeSortTree:
    def __init__(self, lo, hi):
        self.lo, self.hi = lo, hi
        self.data = defaultdict(list)
        self.left = {}; self.right = {}
        self.cnt = 1

    def add(self, nd, lo, hi, x, y):
        bisect.insort(self.data[nd], y)
        if lo == hi: return
        mid = (lo + hi) // 2
        if x <= mid:
            if nd not in self.left: self.left[nd] = self.cnt; self.cnt += 1
            self.add(self.left[nd], lo, mid, x, y)
        else:
            if nd not in self.right: self.right[nd] = self.cnt; self.cnt += 1
            self.add(self.right[nd], mid+1, hi, x, y)

    def count(self, nd, lo, hi, ql, qr, y1, y2):
        if nd is None or ql > hi or qr < lo: return 0
        if ql <= lo and hi <= qr:
            lst = self.data[nd]
            return bisect.bisect_right(lst,y2) - bisect.bisect_left(lst,y1)
        mid = (lo+hi)//2
        return (self.count(self.left.get(nd), lo, mid, ql, qr, y1, y2) +
                self.count(self.right.get(nd), mid+1, hi, ql, qr, y1, y2))

模範解答 (Python)

import sys
import bisect
from collections import defaultdict
input = sys.stdin.readline

class DynamicSegTree:
    def __init__(self, lo, hi):
        self.lo = lo
        self.hi = hi
        self.data = defaultdict(list)
        self.left = {}
        self.right = {}
        self.node_count = 1

    def _new_node(self):
        n = self.node_count
        self.node_count += 1
        return n

    def add(self, node, lo, hi, x, y):
        bisect.insort(self.data[node], y)
        if lo == hi:
            return
        mid = (lo + hi) // 2
        if x <= mid:
            if node not in self.left:
                self.left[node] = self._new_node()
            self.add(self.left[node], lo, mid, x, y)
        else:
            if node not in self.right:
                self.right[node] = self._new_node()
            self.add(self.right[node], mid + 1, hi, x, y)

    def count(self, node, lo, hi, ql, qr, y1, y2):
        if node is None or ql > hi or qr < lo:
            return 0
        if ql <= lo and hi <= qr:
            lst = self.data[node]
            return bisect.bisect_right(lst, y2) - bisect.bisect_left(lst, y1)
        mid = (lo + hi) // 2
        l_node = self.left.get(node)
        r_node = self.right.get(node)
        return (self.count(l_node, lo, mid, ql, qr, y1, y2) +
                self.count(r_node, mid + 1, hi, ql, qr, y1, y2))

    def insert(self, x, y):
        self.add(1, self.lo, self.hi, x, y)

    def query(self, x1, y1, x2, y2):
        return self.count(1, self.lo, self.hi, x1, x2, y1, y2)


def solve():
    Q = int(input())
    COORD_MAX = 10**9
    tree = DynamicSegTree(0, COORD_MAX)
    out = []
    for _ in range(Q):
        line = input().split()
        if line[0] == 'add':
            tree.insert(int(line[1]), int(line[2]))
        else:
            ans = tree.query(int(line[1]), int(line[2]), int(line[3]), int(line[4]))
            out.append(ans)
    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: 問題の難しさ

2D オンライン点追加 + 矩形カウントは「動的 2D データ構造」の典型問題。1D の BIT や SegTree の 2D 版は静的（予め全点を知る必要がある）ケースが多い。オンラインでは動的セグメント木が有効。

Step 2: 動的セグメント木（x軸）

x 座標を管理するセグメント木を辞書ベースで実装（メモリを使ったノードのみ作成）。各ノードは y 座標のソート済みリストを持つ Merge Sort Tree 構造。座標圧縮が不要なため完全にオンラインで動作する。

Step 3: 追加クエリ

点 $(x, y)$ を追加するとき、x に対応する $O(\log N)$ 個のノードすべてに $y$ を二分挿入（bisect.insort）する。計算量は $O(\log^2 N)$（log N ノード × log N 挿入）。

Step 4: カウントクエリ

$[x_1, x_2] \times [y_1, y_2]$ のカウント：x 軸のセグメント木で $[x_1, x_2]$ をカバーするノードを辿り（$O(\log N)$ 個）、各ノードの y リストで bisect_right(y2) - bisect_left(y1) を計算（$O(\log N)$ per node）。合計 $O(\log^2 N)$。

よくあるミス

ミス	原因	正しい書き方
動的セグ木で node=None チェック忘れ	未到達ノードへのアクセス	`if node is None: return 0`
bisect 引数順の間違い	bisect.bisect_right(val, list) と逆に書く	`bisect.bisect_right(list, val)` が正
座標上限を間違える	COORD_MAX より大きい値が来る	問題文の制約 $10^9$ を確認
bisect.insort の O(N) コスト	list の挿入はシフトが O(N)	N が大きい場合は sortedcontainers.SortedList を使用

次のステップ

発展問題: sortedcontainers.SortedList を使わず、B-Tree または Skip List で $O(\log N)$ 挿入を実現し、全体計算量を $O(Q \log^2 Q)$ に保ちながらも定数係数を改善せよ。

自己評価

完全理解おおむね理解要復習