Mo′s Algorithm(クエリ平方分割)について
はじめに区間計算を行う際に累積和やSegment Treeを用いがちですが、それでは上手くいかない問題もあります。
そのような問題の一部を解く手法としてMo′s Algorithmがあります。
次にMo′s Algorithmが使える問題の例を挙げます。
問題$${N}$$個の数$${A_0……A_{N-1}}$$があります。
次の$${Q}$$個のクエリに答えてください。
「$${l,r}$$が与えられるので$${A_l……A_r}$$に含まれる値の種類数を答えよ」
制