题解：P11210 『STA - R8』强制在线动态二维数点

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
const int M=2e6+5;
const int inf=1e8+7;
multiset<int>S[N];
namespace sgt{
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
	int L[M],R[M];
	int mnr[M],mn1[M];
	void pushup(int o){
		mnr[o]=min(mnr[ls],mnr[rs]);
		mn1[o]=min(mn1[ls],mn1[rs]);
	}
	void build(int o,int l,int r){
		L[o]=l,R[o]=r;
		if(l==r){
			mnr[o]=*S[l].begin(),mn1[o]=(*S[l].begin())-l;
			return;
		}
		build(ls,l,mid),build(rs,mid+1,r);
		pushup(o);
	}
	void update(int o,int pos){
		int l=L[o],r=R[o];
		if(l==r){
			mnr[o]=*S[l].begin(),mn1[o]=(*S[l].begin())-l;
			return;
		}
		update(pos<=mid?ls:rs,pos);
		pushup(o);
	}
	int find(int lim){//最后的 sufmin(r<=lim) 的点
		int o=1,l,r,res=0;
		while(1){
			l=L[o],r=R[o];
			if(mnr[o]>lim)break;
			if(l==r){res=l;break;}
			o=(mnr[rs]<=lim?rs:ls);
		}
		return res;
	}
	int qrymn(int o,int lt,int rt){
		int l=L[o],r=R[o];
		if(l>=lt&&r<=rt)return mn1[o];
		int res=inf;
		if(lt<=mid)res=min(res,qrymn(ls,lt,rt));
		if(rt> mid)res=min(res,qrymn(rs,lt,rt));
		return res;
	}
#undef ls
#undef rs
#undef mid
}
int Qry(int L,int R){
	int l=L,r=sgt::find(R);
	if(l>r)return 0;
	int res=sgt::qrymn(1,l,r);
	return (res==inf?0:res);
}
int xs[N],ys[N];
int n,q;
void init(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
		S[i].clear(),S[i].insert(i+inf);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&ys[i],&xs[i]);
		S[xs[i]].insert(ys[i]);
	}
	sgt::build(1,1,n);
	
}
void work(){
	int Ans=0;
	int x,y,i;
	char ops;scanf("\n");
	while(q--){
		scanf("%c",&ops);
		if(ops=='U'){
			scanf("%d%d%d\n",&i,&y,&x);
			i^=Ans,x^=Ans,y^=Ans;
			S[xs[i]].erase(S[xs[i]].find(ys[i]));
			sgt::update(1,xs[i]);
			xs[i]=x,ys[i]=y;
			S[xs[i]].insert(ys[i]);
			sgt::update(1,xs[i]);
		}
		if(ops=='Q'){
			scanf("%d%d\n",&x,&y);
			x^=Ans,y^=Ans;
			Ans=Qry(x,y);
			printf("%d\n",Ans);
		}
	}
}
int main(){
	init();
	work();
	return 0;
}