データ構造を利用して、いわゆる「殴る」解法をいくつか紹介します。

multiset を用いてシミュレートする方法

pair<バージョン, 台数> を multiset で管理しながらシミュレートすることでこの問題に正解できます。
実装例について、時間計算量は \(O((N+Q) \log (N+Q))\) です。

実装例 (C++):

#include<bits/stdc++.h>

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

int main(){
  int n,q;
  cin >> n >> q;
  multiset<pi> st;
  for(int i=1;i<=n;i++){
    st.insert({i,1});
  }
  while(q--){
    int x,y;
    cin >> x >> y;
    int res=0;
    while(!st.empty()){
      auto it=st.begin();
      if((*it).first>x){break;}
      res+=(*it).second;
      st.erase(it);
    }
    if(st.size()>0){ st.insert({y,res}); }
    cout << res << "\n";
  }
  return 0;
}

note: このコード中の multiset を set にすると WA になります。何故でしょうか?

priority_queue を利用する方法

シミュレートに priority_queue を利用しても構いません。
実装例について、時間計算量は \(O((N+Q) \log (N+Q))\) です。

実装例 (C++):

#include<bits/stdc++.h>

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

int main(){
  int n,q;
  cin >> n >> q;
  priority_queue<pi,vector<pi>,greater<pi>> pq;
  for(int i=1;i<=n;i++){
    pq.push({i,1});
  }
  while(q--){
    int x,y;
    cin >> x >> y;
    int res=0;
    while(!pq.empty()){
      if(pq.top().first>x){break;}
      res+=pq.top().second; pq.pop();
    }
    if(res>0){ pq.push({y,res}); }
    cout << res << "\n";
  }
  return 0;
}

lazy_segtree を利用する方法

ACL にも含まれる、 lazy_segtree (遅延伝播セグメント木) を利用することでもこの問題に正解できます。
実装例について、時間計算量は \(O((N+Q) \log N)\) です。

実装例 (C++):

#include<bits/stdc++.h>
#include<atcoder/lazysegtree>

using namespace std;
using namespace atcoder;

using ll=long long;

struct S{
  ll val,len;
};
using F=ll;

const F ID=8e18;

S op(S a,S b){ return {a.val+b.val,a.len+b.len}; }
S e(){ return {0,0}; }
S mapping(F f,S x){
  if(f!=ID){ x.val=f*x.len; }
  return x;
}
F composition(F f,F g){ return (f==ID)?g:f; }
F id(){ return ID; }

int main(){
  ll n,q;
  cin >> n >> q;
  vector<S> v(n+1,{1,1});
  v[0]={0,1};
  lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);

  while(q--){
    ll x,y;
    cin >> x >> y;
    ll res=seg.prod(0,x+1).val;
    seg.apply(0,x+1,0);
    seg.set(y,{seg.get(y).val+res,1});
    cout << res << "\n";
  }
  return 0;
}