2022-10-15から1日間の記事一覧

Static Range Inversions Query

前置き judge.yosupo.jp を解いたのでメモ。前計算 $O(N\sqrt{N})$、クエリ $O(\sqrt N)$ で解きます。 問題 長さ $N$ の整数列 $A=(A _ 0, \ldots, A _ {N-1})$ が与えられる。以下のクエリを $Q$ 個処理せよ: l r : $A$ の連続部分列 $A _ l A _ {l+1} \cd…