【悬 2 关】20pts 求调

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int n,m,w,a[maxn],tr[maxn<<2],cnt,pre[maxn];
set<int>v[maxn];
void push_up(int id){
	tr[id]=max(tr[id<<1],tr[id<<1|1]);
}
void build(int l,int r,int id){
	if(l==r){
		tr[id]=pre[l];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,id<<1);
	build(mid+1,r,id<<1|1);
	push_up(id);
}
void update(int x,int s,int t,int id,int val){
	if(s==t){
		tr[id]=val;
		return;
	}
	int mid=s+t>>1;
	if(x<=mid) update(x,s,mid,id<<1,val);
	else update(x,mid+1,t,id<<1|1,val);
	push_up(id);
}
int query(int l,int r,int s,int t,int id){
	if(s>=l && t<=r) return tr[id];
	int mid=s+t>>1,ans=0;
	if(l<=mid) ans=max(ans,query(l,r,s,mid,id<<1));
	if(r>mid) ans=max(ans,query(l,r,mid+1,t,id<<1|1));
	return ans;
}
void modify(int x,int val){
	auto it1=v[val].find(x);
	auto it2=v[w-val].lower_bound(x);
	if(it2==v[w-val].begin()){
		pre[x]=0;
		update(x,1,n,1,pre[x]);
	}
	else{
		if(val*2==w){
			pre[x]=*(--it2);
			update(x,1,n,1,pre[x]);
		}
		else if(it1==v[val].begin() || *(--it1)<=*(--it2)){
			pre[x]=*it2;
			update(x,1,n,1,pre[x]);
		}
		else{
			pre[x]=0;
			update(x,1,n,1,pre[x]);
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>w;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		if(!v[w-a[i]].empty()) pre[i]=*(--v[w-a[i]].end());
		else pre[i]=0;
		v[a[i]].insert(i);
	}
	build(1,n,1);
	while(m--){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			int z=a[x];
			auto it=v[z].upper_bound(x);
			if(it!=v[z].end()) modify(*it,z);
			it=v[w-z].upper_bound(x);
			if(it!=v[w-z].end()) modify(*it,w-z);
			a[x]=y;
			v[z].erase(x);
			v[y].insert(x);
			it=v[y].upper_bound(x);
			if(it!=v[y].end()) modify(*it,y);
			it=v[w-y].upper_bound(x);
			if(it!=v[w-y].end()) modify(*it,w-y);
			modify(x,y);
		}
		else{
			x^=cnt;
			y^=cnt;
			int ret=query(x,y,1,n,1);
			if(ret>=x){
				cout<<"Yes\n";
				cnt++;
			}
			else cout<<"No\n";
		}
	}
	return 0;
}