この解説では、時間計算量 \(O(N+Q)\) の方針を示します。
他の方針も (計算量が少し悪くなるものも含めて) 多く存在します。

まず、バージョン \(X\) 以前の PC をバージョン \(Y\) にアップグレードした時に起きることを整理しましょう。

• 現在の PC のうち最古のバージョンを \(O\) とすると、 \(O\) 以上 \(X\) 以下の全てのバージョンの PC がアップグレードの対象となる。
• 制約より \(X<Y\) なので、このアップグレードが終わると、 \(X\) 以前のバージョンの PC は存在しなくなる。
  • 以降のアップデートに対して、 \(O=X+1\) 以上になる。

このことから、最古のバージョン \(O\) に着目しながらアップグレードを行うと高速にアップグレードを処理できそうです。

ここから、以下の解法が成り立ちます。

• 最初、最古のバージョンは \(O=1\) である。
• \(i=1,2,\dots,Q\) について、 \(i\) 回目の操作を行う。
  • \(X_i < O\) である時、 \(X_i\) 以前のバージョンの PC はもう存在しないのでこの操作をスキップする。
  • そうでない時、 \(O \le X_i\) である限り次の操作を繰り返す。
    • バージョン \(O\) の PC を全てバージョン \(Y_i\) にアップグレードする。
    • その後、 \(O \rightarrow O+1\) とする。

一連の解法は、配列とループの組み合わせで表現できます。

実装例 (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;
}