Day 157-Q4 — 並列二分探索 + BIT（複数閾値クエリの一括処理）

2026-09-18 赤色 Master / Phase 8+ ★★★★★★★★★ O((T+Q)log T log N) で複数クエリの時刻二分探索を一括化

問題

$N$個の貯水池が横一列に並んでいる。$T$回の降雨イベントが時刻$1,\dots,T$の順に発生し、時刻$t$のイベントは区間$[l_t,r_t)$の貯水池すべてに$x_t$だけ雨水を加える（$x_t>0$）。

$Q$個の質問（貯水池$p_i$、しきい値$X_i$）それぞれについて、貯水池$p_i$の累積雨量が初めて$X_i$以上になる時刻を求めよ（届かなければ$-1$）。

入力形式

N T
l_1 r_1 x_1
...
l_T r_T x_T
Q
p_1 X_1
...
p_Q X_Q

制約

$1 \le N,T,Q \le 2\times10^3$
$0 \le l_t < r_t \le N$
$1 \le x_t \le 10$
$1 \le X_i \le 5000$

入出力例

入力例1

6 5
0 3 4
2 6 3
0 2 5
1 5 2
0 6 1
4
0 9
2 7
5 3
3 100

出力例1

3
2
2
-1

概念図：時刻軸を1ラウンドにつき1回だけ舐める

1ラウンド：時刻1..Tを1回だけ走査し、各質問のmidで判定 t=1 t=2 t=3 t=4 t=5 質問A: mid=3 → BITで判定 質問B: mid=2 → BITで判定 同じ時刻軸の走査で複数質問のmidを同時に処理 → O(T+Q) / ラウンド

ヒント（段階的開示）

ヒント1（方向性）

質問ごとに素朴に「時刻について二分探索し、そのたびに時刻1からすべて再生」すると$O(QT\log T)$になり重い。二分探索の「時刻軸を舐め直す」部分を質問間で共有できないか考える。

ヒント2（アプローチ）

「答えの条件が時刻について単調」なとき、複数の質問の二分探索を同時に進められる。各質問は探索区間$[\mathrm{lo}_i,\mathrm{hi}_i]$を持ち、中間点$\mathrm{mid}_i$を知りたいだけ。時刻を$1$から$T$まで1回だけ舐めながら、通過中の時刻がどれかの質問の中間点と一致したらその質問だけ判定する——これを$\log T$ラウンド繰り返す。

ヒント3（誘導） 
# 1ラウンドの処理
# 1. mid[i] = (lo[i]+hi[i])//2 を計算し mid の値でバケツにまとめる
# 2. 空のBITから時刻1..Tまで進め、イベント反映しつつ、
#    tがバケツに入っていればそのバケツの質問すべてを判定してlo/hiを更新

模範解答 (Python)

import sys

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)

    def prefix_sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s


class DiffBIT:
    def __init__(self, n):
        self.n = n
        self.b1 = BIT(n)
        self.b2 = BIT(n)

    def range_add(self, l, r, x):
        self.b1.add(l, x); self.b1.add(r, -x)
        self.b2.add(l, x * l); self.b2.add(r, -x * r)

    def prefix_sum(self, i):
        return (i + 1) * self.b1.prefix_sum(i) - self.b2.prefix_sum(i)

    def point_value(self, i):
        return self.prefix_sum(i) - (self.prefix_sum(i - 1) if i > 0 else 0)


def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    events = {}
    for t in range(1, T + 1):
        l, r, x = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
        events.setdefault(t, []).append((l, r, x))
    Q = int(data[idx]); idx += 1
    queries = []
    for _ in range(Q):
        p, X = int(data[idx]), int(data[idx+1]); idx += 2
        queries.append((p, X))

    lo = [1] * Q
    hi = [T + 1] * Q

    rounds = T.bit_length() + 2
    for _ in range(rounds):
        if all(lo[i] >= hi[i] for i in range(Q)):
            break
        buckets = {}
        mid_of = [None] * Q
        any_active = False
        for i in range(Q):
            if lo[i] < hi[i]:
                any_active = True
                mid = (lo[i] + hi[i]) // 2
                mid_of[i] = mid
                buckets.setdefault(mid, []).append(i)
        if not any_active:
            break

        bit = DiffBIT(n)
        for t in range(1, T + 1):
            for (l, r, x) in events.get(t, []):
                bit.range_add(l, r, x)
            if t in buckets:
                for i in buckets[t]:
                    p, X = queries[i]
                    if bit.point_value(p) >= X:
                        hi[i] = mid_of[i]
                    else:
                        lo[i] = mid_of[i] + 1

    out = []
    for i in range(Q):
        out.append(str(lo[i]) if lo[i] <= T else "-1")
    print('\n'.join(out))

solve()

Step-by-Step 解説

1単調性が前提
雨水しか加わらないため「累積値が$X$以上」は一度真になったらずっと真という単調性を持つ。この性質がないと二分探索が成立しない。
2質問ごと→時刻ごとへの転置
「時刻軸を舐める」作業をラウンドあたり1回にまとめ、その中で全質問の「今知りたい中間点」を一度に処理する。
3バケツ分けの役割
同じ$\mathrm{mid}$を持つ質問をまとめておき、時刻$t$を通過するときに「$t$をちょうど知りたがっている質問」だけを判定する。
4実測（本ページ作成時にPythonで実行）
テスト内容結果
入力例1並列BS [3,2,2,-1] / 逐次再生 [3,2,2,-1] 一致
ランダム150件逐次再生との不一致 0件
N=T=Q=2000並列BS 0.099s / 逐次再生 12.612s（約127倍）

迷った他案と採らなかった理由

案採否理由
質問ごとに逐次で二分探索（毎回時刻を再生）不採用$O(QT\log T)$。$N=T=Q=2000$で実測12.6秒、実用的でない
並列二分探索 + Union-Find（Day028方式）不採用（今回は別対象）本問は「区間加算・点参照」の集計が必要で、Union-Findでは表現できない
並列二分探索 + 差分BIT（本ページ採用）採用区間加算・点参照が$O(\log N)$で行え、単調性のある閾値クエリと相性が良い

よくあるミス

ミス原因正しい書き方
ラウンドごとにBITを使い回す「前のラウンドの状態を引き継げば速そう」という誤解各ラウンドの最初に必ず新しいBITを作り直す
hiの初期値をTにする「見つからなかった」を表現できない番兵としてhi=T+1を使う
同じmidの質問を1つずつ処理バケツ化を怠るmidでバケツ分けし、その場でまとめて処理
終了判定を怠り無限ループ収束した質問も毎回中間点を計算lo[i]<hi[i]のときだけ計算し早期終了する

次のステップ

  • 発展: イベントに負の量（蒸発）を許すと単調性が崩れる具体例を作る
  • 発展2: BITの代わりにセグメント木（区間加算・区間最小値）に載せ替える
  • 扱わなかった範囲: 負のイベントを含む一般化
  • 次回予告: 並列二分探索 + Segment Tree Beats の組み合わせ

自己評価

自分の回答

気づき・メモ