問題リンク
問題概要
\(N\)要素の数列\(c_1,...,c_N\)が与えられる。
以下の\(Q\)個のクエリを処理せよ。
- クエリ\(i\)：\(c_{l_i}\)から\(c_{r_i}\)までの要素の種類数を答える。
解法
要素数は\(r_i - l_i + 1\)なので、これから同じ要素が重複している分だけ引くことを考える。
\(c_j=c_k\)かつ\(j\)と\(k\)の間に同じ値の要素が存在しないような全てのペアに対し、
区間\([l_i,r_i]\)が\([j,k]\)を完全に含んでいるようなペアの個数を引く、という方針で考える。
上のような\( (j,k) \)の組み合わせは\(O(N)\)個あるので、効率的に処理する必要がある。
また、「区間を完全に含んでいる」は「\(l_i \leq j \)かつ\(k \leq r_i\)」という2つの条件が絡んでいるので面倒である。
こういう時は、片方の条件が常に成り立つようにソートをして点を追加しつつクエリに答えることで上手くいくことがある。今回の場合、
- 全ての区間(\([l_i,r_i]\)と\([j,k]\)たち)を左端に関して降順にソート。
- ただし等しい場合は\([j,k]\)が先にくるようにする。
- \([l_i,r_i]\)が来た時は、それまでに登場した\(c_k\)のうち\(r_i\)以下であるような物の個数が含まれる区間の個数なので、i番目のクエリの答えは\( (r_i - l_i + 1) \)からその個数を引いたものになる。
左端の降順に並べたことで、それまでに追加された点に対し\(l_i \leq j\)が常に成り立っていることが肝心である。
後は、点を追加しつつ、ある値以下の点の個数を答えればよいので、これはBITを使えば求められる。
提出
https://atcoder.jp/contests/abc174/submissions/15624952
感想
最初累積和の変形で考えたのでかなりタイムロスした。
上位陣がめちゃくちゃ速いし典型っぽい。
(追記：Mo's algrorithmというのがあるそうです)
