ABC170-E

e.cpp

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N,Q;cin>>N>>Q;
  vector<int> rate(N+1);
  vector<int> belong(N+1);
  vector<multiset<int>> youchien(200010);
  multiset<int> maxenji;

  for(int i=1; i<=N; i++){
    int a,b;cin>>a>>b;
    rate[i] = a;
    belong[i] = b;
    youchien[b].insert(a);
  }

  for(auto x: youchien){
    if(x.empty())continue;
    maxenji.insert(*x.rbegin());
  }
  
  for(int i=1; i<=Q; i++){
    int c,d;cin>>c>>d;
    int F = belong[c];
    int T = d;
    
    maxenji.erase(*youchien[F].rbegin());
    if(!youchien[T].empty()){
      maxenji.erase(*youchien[T].rbegin());
    }
    
    youchien[F].erase(rate[c]);
    youchien[T].insert(rate[c]);
    
    if(!youchien[F].empty()){
      maxenji.insert(*youchien[F].rbegin());
    }
    maxenji.insert(*youchien[T].rbegin());
    
    belong[c] = T;
    cout<<*maxenji.begin()<<endl;
  }
}