アルゴリズム忘備録

競技プログラミングとかデータ分析とか

2017-04-15から1日間の記事一覧

Mo's Algorithm

前これを使う問題をCodeforcesでみた(解けなかった)のでメモ。 a[1] ... a[N] (N=O(10^6)) に対し区間クエリQ(l, r)がO(10^6)個発行される。このクエリは先読み可能である。Q(l, r)の結果がわかっているときに隣接クエリQ(l±1, r), Q(l, r±1) の結果はO(1)と…