AtCoder ABC 210 C - Colorful Candies (3Q, 灰色, 300 点)

区間を伸ばしたり縮めたりしながら、それに伴う「挿入」や「削除」に対処するデータ構造を考える系の問題！

• 問題へのリンク

問題概要

数列 について、連続する 個の要素の種類数の最大値を答えよ。

制約

• 

考えたこと

数列の幅 の区間をすべて調べるには、次のようにやるのが定石だ。なお、区間内のデータを管理するデータ構造があるとする。

---

• まず、数列の先頭から 個の要素を順に、データ構造に「挿入」する（この時の種類数を記録する）
• その後は、次のことを繰り返す
  • 区間の右端より 1 歩先の要素を、データ構造に「挿入」する
  • 区間の左端の要素を、データ構造から「削除」する
  • その後、種類数を記録する

---

以上のことができるためには、次の処理を高速にこなせるデータ構造があればよい。

• データ構造に要素 を挿入する
• データ構造から要素 を削除する
• データ構造に格納されている要素の種類数を答える

これらがすべてこなせるデータ構造として、今回は map<int, int> 型の変数 nums を用いることとした。具体的には

• nums[x]：データ構造に格納されている値 の要素の個数

とする。

これによって、上記の処理を実行すると、計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> c(N);
    for (int i = 0; i < N; i++) cin >> c[i];

    map<int, int> nums;
    auto insert = [&](int x) -> void {
        nums[x]++;
    };
    auto erase = [&](int x) -> void {
        nums[x]--;
        if (nums[x] == 0) nums.erase(x);
    };

    int res = 0;
    for (int i = 0; i < N; i++) {
        insert(c[i]);
        if (i >= K) erase(c[i-K]);
        res = max(res, (int)nums.size());
    }
    cout << res << endl;
}