你这衣服租来的吗

一道简单的数据结构题。
题目要区间赋值，所以使用颜色段均摊。
使用一个set维护相同颜色的连续区间。
维护若干个线段树，线段树的下标(i)表示：如果线段树上当前位置的颜色等于线段树对应的颜色，则该下标处的值为1，否则为0。
更新这些线段树可以使用区间加法。
在set更新区间的时候顺便在线段树上加法。
查询时可以在对应颜色的线段树上二分。
时间复杂度(O((n+q)log_2n))

#include<bits/stdc++.h>
using namespace std;
#define N 500010
int n,m,rt[N],a[N],lc[N*30],rc[N*30],s[N*30],tg[N*30],ct,sl[N],tp,tl[N],tr[N],cc;
void pd(int o,int l,int r){
	if(tg[o]){
		int md=(l+r)/2;
		if(!lc[o])
			lc[o]=++ct;
		if(!rc[o])
			rc[o]=++ct;
		s[lc[o]]+=(md-l+1)*tg[o];
		s[rc[o]]+=(r-md)*tg[o];
		tg[lc[o]]+=tg[o];
		tg[rc[o]]+=tg[o];
		tg[o]=0;
	}
}
struct no{
	int l,r,z;
};
int operator <(no x,no y){
	return x.r<y.r;
}
set<no>st;
set<no>::iterator it,ii,iv;
map<int,int>ma;
void sp(int x){
	it=st.lower_bound((no){0,x});
	no p=*it;
	if(p.l!=x){
		st.erase(it);
		st.insert((no){p.l,x-1,p.z});
		st.insert((no){x,p.r,p.z});
	}
}
void ad(int &o,int l,int r,int x,int y,int z){
	if(!o)
		o=++ct;
	if(r<x||y<l)
		return;
	if(x<=l&&r<=y){
		tg[o]+=z;
		s[o]+=z*(r-l+1);
		return;
	}
	pd(o,l,r);
	int md=(l+r)/2;
	ad(lc[o],l,md,x,y,z);
	ad(rc[o],md+1,r,x,y,z);
	s[o]=s[lc[o]]+s[rc[o]];
}
int k;
int ef(int o,int l,int r,int k){
	if(l==r)
		return l;
	int md=(l+r)/2;
	pd(o,l,r);
	if(s[lc[o]]>=k)
		return ef(lc[o],l,md,k);
	k-=s[lc[o]];
	return ef(rc[o],md+1,r,k);
}
void qp(int o,int l,int r,int x,int y){
	if(!o)
		return;
	if(r<x||y<l)
		return;
	if(x<=l&&r<=y){
		sl[++tp]=o;
		tl[tp]=l;
		tr[tp]=r;
		return;
	}
	int md=(l+r)/2;
	pd(o,l,r);
	qp(lc[o],l,md,x,y);
	qp(rc[o],md+1,r,x,y);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!ma.count(a[i])){
			ma[a[i]]=++cc;
			a[i]=cc;
		}
		else
			a[i]=ma[a[i]];
		st.insert((no){i,i,a[i]});
		ad(rt[a[i]],1,n,i,i,1);
	}
	int la=0;
	for(int i=1;i<=m;i++){
		char c[5];
		scanf("%s",c);
		if(c[0]=='M'){
			int l,r,z;
			scanf("%d%d%d",&l,&r,&z);
			l^=la;
			r^=la;
			z^=la;
			if(!ma.count(z)){
				ma[z]=++cc;
				z=cc;
			}
			else
				z=ma[z];
			sp(l);
			if(r+1<=n)
				sp(r+1);
			it=st.lower_bound((no){0,l});
			ii=st.lower_bound((no){0,r+1});
			for(;it!=ii;it++){
				no x=*it;
				ad(rt[x.z],1,n,x.l,x.r,-1);
				ad(rt[z],1,n,x.l,x.r,1);
			}
			it=st.lower_bound((no){0,l});
			for(;it!=ii;){
				iv=it;
				it++;
				st.erase(iv);
			}
			st.insert((no){l,r,z});
		}
		else{
			int l,r,v;
			scanf("%d%d%d%d",&l,&r,&k,&v);
			l^=la;
			r^=la;
			k^=la;
			v^=la;
			if(!ma.count(v)){
				ma[v]=++cc;
				v=cc;
			}
			else
				v=ma[v];
			tp=0;
			qp(rt[v],1,n,l,r);
			int ok=0;
			for(int i=1;i<=tp;i++){
				if(s[sl[i]]<k)
					k-=s[sl[i]];
				else{
					la=ef(sl[i],tl[i],tr[i],k);
					ok=1;
					printf("%d
",la);
					break;
				}
			}
			if(!ok){
				la=0;
				puts("0");
			}
		}
	}
	puts("");
}