Decompose the information on each bird into the following three events:

• In the beginning, a bird of color \(A_i\) increases by one.
• On day \(D_i\), a bird of color \(A_i\) decreases by one.
• On day \(D_i\), a bird of color \(B_i\) increases by one.

Now the events are described by increases/decreases of birds, which are easy to handle.

These events can be handled by maintaining the following parameters:

• \(kind\): the number of distinct colors of birds
• \(C_k\): the number of birds of color \(k\)

If a bird of color \(k\) increases by one:

• If \(C_k=0\), add \(1\) to \(kind\).
• Add \(1\) to \(C_k\).

If a bird of color \(1\) decreases by one:

• Subtract \(1\) from \(C_k\).
• If \(C_k=0\), subtract \(1\) from \(kind\).

Notes: these operations are inverse operations of each other. It is necessary that applying one operation and then the other must reconstruct the original state, and indeed it does.
This property helps verifying if the algorithm you designed is valid.

Therefore, the overall problem can be solved by the following steps:

• While receiving the information of birds, record the events of color changes on day \(D_i\).
  • In the same manner as the bucket sort, maintain an array of the color update events for each event, and insert them to the array corresponding to day \(D_i\).
• For \(i=1,2,\dots,N\), do the following.
  • Reflect the color update events that occur on day \(i\).
  • The solution for day \(i\) is the number of distinct bird colors at this point.

The time complexity of this solution is \(O(N+M)\).

Sample code (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;
}