This editorial introduces a solution running in \(O(N+Q)\) time.
There are various other approaches (including those with slightly worse complexity).

First, let us consider what happens when PCs with version \(X\) or prior is upgraded to version \(Y\):

• Let \(O\) be the oldest among the current versions. Then all PCs with versions between \(O\) and \(X\) will be upgraded.
• Since the constraints guarantee \(X<Y\), as a result of this upgrade, there will no longer be a PC of version \(X\) or prior.
  • For the later upgrades, \(O\) is always \(X+1\) or greater.

This suggests that we can process upgrades fast by tracking the oldest version \(O\).

Thus we obtain the following solution:

• First, the oldest version is \(O=1\).
• For \(i=1,2,\dots,Q\) in order, perform the \(i\)-th operation.
  • If \(X_i < O\), there is no PC with version \(X_i\) or prior, so skip this operation.
  • Otherwise, repeat the following while \(O \le X_i\).
    • Upgrade all PCs with version \(O\) to \(Y_i\).
    • Then, let \(O \rightarrow O+1\).

This solution can be implemented by combining arrays with loops.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> pc(n+1,1);
  pc[0]=0;
  int o=1;
  while(q--){
    int x,y;
    cin >> x >> y;
    int res=0;
    while(o<=x){
      res+=pc[o];
      pc[y]+=pc[o];
      o++;
    }
    cout << res << "\n";
  }
  return 0;
}