鳥の情報を以下の通りに分解して読み取ります。

• 初期状態に色 \(A_i\) の鳥が \(1\) 羽増える。
• \(D_i\) 日目に色 \(A_i\) の鳥が \(1\) 羽減る。
• \(D_i\) 日目に色 \(B_i\) の鳥が \(1\) 羽増える。

これで、「鳥が \(1\) 羽増える」「鳥が \(1\) 羽減る」という扱いやすい形になりました。

次の情報を持つと、各情報を以下の通りに処理できます。

• 現在の鳥の色の種類数 \(kind\)
• 色 \(k\) の鳥の数 \(C_k\)

色 \(k\) の鳥が \(1\) 羽増える場合:

• \(C_k=0\) なら \(kind\) に \(1\) 加算する。
• \(C_k\) に \(1\) 加算する。

色 \(k\) の鳥が \(1\) 羽減る場合:

• \(C_k\) から \(1\) 減算する。
• \(C_k=0\) なら \(kind\) から \(1\) 減算する。

メモ: この \(2\) つは互いに逆操作の関係にあります。一方をかけた後もう一方をかけると元の状態に戻ることが必要ですし、現にそのようになることが確認できます。
この性質を利用することで、自身の設計した操作が正当かどうかをある程度検討できます。

結局、本問題全体は以下のように解くことができます。

• 鳥の情報を受け取りながら、鳥の色の変化の情報を \(D_i\) 日目に記録する。
  • バケットソートの要領で、各日の「色の変化の情報たちを表す配列」の配列を保持し、 \(D_i\) 日目にあたる部分に色の変化の情報を追加する方法があります。
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • \(i\) 日目に起きる鳥の色の変化(鳥の増加・減少)を反映させる。
  • この時点での鳥の色の種類数が \(i\) 日目時点での解である。

本解法の時間計算量は \(O(N+M)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int n,m;
  cin >> n >> m;
  int kind=0;
  vector<int> cnt(n+1);
  vector<vector<pi>> change(m+1);
  for(int i=0;i<n;i++){
    int a,b,d;
    cin >> a >> d >> b;
    if(cnt[a]==0){kind++;}
    cnt[a]++;
    change[d].push_back({a,b});
  }
  for(int i=1;i<=m;i++){
    for(auto &nx : change[i]){
      cnt[nx.first]--;
      if(cnt[nx.first]==0){kind--;}
      if(cnt[nx.second]==0){kind++;}
      cnt[nx.second]++;
    }
    cout << kind << "\n";
  }
  return 0;
}