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; }