ACLのセグ木上の二分探索の条件判定にはprodの結果が使われるぜ！(1敗)

2025-01-20

ABC389-Fで(遅延)セグメント木上の二分探索が使える問題が出た。

結果的にACできたもののアホみたいな先入観込みで手こずってしまったのでメモに残しておく。

ac-library-pythonの max_right は max_right(0, lambda x: x <= r) のような形式で、左端の下限(min_leftの場合右端の上限)と関数を引数として与える。

このとき、与えた関数を $f$ として、 $f(prod(l, r)) = True$ となるような最大の $r$ を求める。

しかし、哀れな自分はABC389-Fの問題の性質上要素が単調増加している上に一点取得ができれば十分なこと、配列上の二分探索(Python標準のbisect_leftとbisect_right)の先入観が重なり、
あろうことか $f(get(r)) = True$ となるような最大の $r$ をよしなに返してくれるものと勝手に勘違いしていた。
今思えばどう考えても一般化できないだろ。単調性のある配列しかセグ木に乗せたことないんかお前は。

$f$ 自体もprodの結果が単調になるように与えるべきであり、また $f(e) = True$ でなければならない。

そんな関数に「ｳｰﾝ、それっぽく min_leftに lambda x: x >= l 、max_rightに lambda x: x <= r とか渡せばいけるんちゃう？ｗ」とかやりだすと $f(e)$ の整合性すらとれなくなる。あたりめーだ。

そんなこんなで、仕様を知らないまま雰囲気でmin_leftを使用してRE -> 自分で実装 -> バグる -> 時間を溶かすのコンボで瓦2つ分くらいperfを落としましたとさ。

以下は記事を書く前にACしなおしたコード。
min_left、min_rightはいずれもf(e)がTrueになる必要があるので、「 $l$ 以上の左端」の代わりに「 $l-1$ 以下の右端」として統一しようmax_rightで統一しよう。

なお、遅延セグ木は定数倍が重いことで有名(?)なので座標圧縮みたいなことをしているが、 list(range(0, 500000)) の遅延セグ木でも通るっぽい。

from atcoder import lazysegtree

import sys

input = sys.stdin.readline

N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)]
Q = int(input())
queries = [[i, int(input())] for i in range(Q)]

queries.sort(key=lambda x: x[1])
values = [q[1] for q in queries]

INF = 10**18
op = lambda x, y: max(x, y)
e = -INF
mapping = lambda f, x: f + x
composition = lambda f, g: f + g
id_ = 0
lst = lazysegtree.LazySegTree(op, e, mapping, composition, id_, values)

for l, r in LR:
    i = lst.max_right(0, lambda x: x <= l - 1)
    j = lst.max_right(0, lambda x: x <= r)
    lst.apply(i, j, 1)

results = [lst.get(i) for i in range(Q)]

ans = [0] * Q
for i in range(Q):
    ans[queries[i][0]] = results[i]

print(*ans, sep="\n")