分割統治法

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\) ABC282F 解法 0: Sparse table 長さ \(2^{i}\) の区間を用意して，それらの組み合わせで 区間を覆うことができる． 区間を指定されたとき，sarse table から使う幅 \(w\) を全探索する． \([l, l+w) \cup [r-w, r) = [l,r)\) となる \(w\) を見つける． \(w\) を小さい方から探していき，初めて覆っているもので break. 解法 1: 分割統治法 分割統治なら，disjoint union で区間を書くことが出来る． 区間を真…