求HACK

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
struct node{
	int maxx,ls,rs;
}tr[45*N+5];
struct node1{
	int b,maxx;
	node1(){};
	node1(int x,int y):b(x),maxx(y){};
	bool operator>(const node1 &c) const{
		return maxx>c.maxx;
	}
};
int n,m;
int a[N+5],b[N+5],cntb[N+5];
int root[N+5],sz;
int ans[N+5];
priority_queue<node1,vector<node1>,greater<node1> > q;
void change(int &p,int x,int y,int l,int r){
	if(!p){
		p=++sz;
	}
	if(l==y && r==y){
		tr[p].maxx=x;
		return;
	}
	int mid=(l+r)>>1;
	if(y<=mid) change(tr[p].ls,x,y,l,mid);
	else change(tr[p].rs,x,y,mid+1,r);
	tr[p].maxx=max(tr[tr[p].ls].maxx,tr[tr[p].rs].maxx);
	return;
}
int search(int x){
	return tr[root[x]].maxx;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
		cntb[b[i]]++;
	}
	for(int i=1;i<=n;i++){
		change(root[b[i]],a[i],i,1,n);
	}
	for(int i=1;i<=N;i++){
		if(cntb[i]){
			int num=search(i);
			q.push(node1(i,num));
			ans[i]=num;
		}
	}
	while(m--){
		int x,y;
		scanf("%lld%lld",&x,&y);
		change(root[b[x]],0,x,1,n);
		change(root[y],a[y],x,1,n);
		ans[b[x]]=search(b[x]);
		ans[y]=search(y);
		cntb[b[x]]--,cntb[y]++;
		if(cntb[b[x]]>0) q.push(node1(b[x],ans[b[x]]));
		if(cntb[y]>0) q.push(node1(y,ans[y]));
		while(!q.empty() && (q.top().maxx!=ans[q.top().b] || q.top().maxx==0)){//感觉q.top().maxx!=ans[q.top().b]判了应该没问题
			q.pop();
		}
		printf("%lld\n",q.top().maxx);
	}
	return 0;
}