Day 082-Q5 — オンライン平面点追加・矩形カウント（Fractional Cascading + Merge Sort Tree）

問題

2次元平面上でオンライン操作を処理せよ：

• add x y: 点 $(x, y)$ を追加
• count x1 y1 x2 y2: $x_1 \le x \le x_2$ かつ $y_1 \le y \le y_2$ を満たす点の個数を答える（XOR オンライン形式）

入出力例

8
A 1 2
A 3 4
A 2 3
C 1 1 3 4
A 4 1
C 1 0 4 3
A 0 0
C 0 0 5 5

3
2
5

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

ヒント

import bisect

class Node:
    __slots__ = ['left', 'right', 'ys']
    def __init__(self):
        self.left = self.right = None
        self.ys = []

def add(node, lo, hi, x, y):
    bisect.insort(node.ys, y)  # ソート維持挿入
    if lo == hi: return
    mid = (lo + hi) >> 1
    if x <= mid:
        if node.left is None: node.left = Node()
        add(node.left, lo, mid, x, y)
    else:
        if node.right is None: node.right = Node()
        add(node.right, mid+1, hi, x, y)

模範解答

import sys
import bisect
input = sys.stdin.readline

def solve():
    Q = int(input())

    class Node:
        __slots__ = ['left', 'right', 'ys']
        def __init__(self):
            self.left = self.right = None
            self.ys = []

    X_MAX = 10**9

    def add(node, lo, hi, x, y):
        bisect.insort(node.ys, y)
        if lo == hi: return
        mid = (lo + hi) >> 1
        if x <= mid:
            if node.left is None: node.left = Node()
            add(node.left, lo, mid, x, y)
        else:
            if node.right is None: node.right = Node()
            add(node.right, mid+1, hi, x, y)

    def query(node, lo, hi, x1, x2, y1, y2):
        if node is None or x2 < lo or hi < x1: return 0
        if x1 <= lo and hi <= x2:
            return bisect.bisect_right(node.ys, y2) - bisect.bisect_left(node.ys, y1)
        mid = (lo + hi) >> 1
        return (query(node.left, lo, mid, x1, x2, y1, y2) +
                query(node.right, mid+1, hi, x1, x2, y1, y2))

    root = Node()
    xor_acc = 0
    out = []

    for _ in range(Q):
        line = input().split()
        op = line[0]
        if op == 'A':
            x, y = int(line[1]), int(line[2])
            add(root, 0, X_MAX, x, y)
        else:
            x1 = int(line[1]) ^ xor_acc
            y1 = int(line[2]) ^ xor_acc
            x2 = int(line[3]) ^ xor_acc
            y2 = int(line[4]) ^ xor_acc
            if x1 > x2: x1, x2 = x2, x1
            if y1 > y2: y1, y2 = y2, y1
            ans = query(root, 0, X_MAX, x1, x2, y1, y2)
            out.append(ans)
            xor_acc = ans

    print('\n'.join(map(str, out)))

solve()

Step-by-Step 解説

Step 1: 動的 Merge Sort Tree の構造

各ノードはカバー範囲内に追加された全点の $y$ 座標をソート済みリストで保持する。ポインタベースにより未訪問ノードはメモリ不使用。

Step 2: add 操作

$x$ の位置に対して根から葉まで降りる経路上の全ノード（深さ $O(\log C)$）の ys に $y$ を bisect.insort で挿入。

Step 3: count クエリ

$x$ 区間を $O(\log C)$ ノードに分解し、各ノードの ys で $[y_1, y_2]$ 内の要素数を二分探索（$O(\log Q)$）で求める。合計 $O(\log^2 C)$。

Step 4: 計算量まとめ

よくあるミス

次のステップ

• 発展問題: 同様の構造で「加重点」のカウント（各点に重みがある場合）
• 参考: Fractional Cascading を使うと $O(\log C)$ クエリも理論的に可能（実装が複雑）

自己評価