hitoare https://blog.hatena.ne.jp/hitoare/ hitoare日記 https://hitoare.hatenablog.com/ 競技プログラミング AtCoder ABC 問題リンク atcoder.jp 問題概要 \(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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fhitoare.hatenablog.com%2Fentry%2F2020%2F08%2F02%2F224034" title="F - Range Set Query(AtCoder Beginner Contest 174) - hitoare日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2020-08-02 22:40:34 rich https://hitoare.hatenablog.com/entry/2020/08/02/224034 1.0 100%