#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
int n,m,a[500005];
struct tree{
	int sz,val,key,ls,rs;
}tr[1000005];
int rot[1000005],tot,cnt;
map<int,int> p;
int get(int x){
	tr[++tot].sz=1;
	tr[tot].val=rnd();
	tr[tot].key=x;
	return tot;
}
void push_up(int pos){
	tr[pos].sz=tr[tr[pos].ls].sz+tr[tr[pos].rs].sz+1;
}
void split(int pos,int x,int &l,int &r){
	if(!pos){
		l=r=0;
		return ;
	}
	if(tr[pos].key<=x){
		l=pos;
		split(tr[l].rs,x,tr[l].rs,r);
	}else{
		r=pos;
		split(tr[r].ls,x,l,tr[r].ls);
	}
	push_up(pos);
}
int merge(int l,int r){
	if(l==0 || r==0)return l+r;
	if(tr[l].val<=tr[r].val){
		tr[l].rs=merge(tr[l].rs,r);
		push_up(l);
		return l;
	}else{
		tr[r].ls=merge(l,tr[r].ls);
		push_up(r);
		return r;
	}
}
void insert(int id,int x){
	int p=0,q=0;
	split(rot[id],x-1,p,q);
	rot[id]=merge(merge(p,get(x)),q);
}
void del(int id,int x){
	int p=0,q=0,r=0;
	split(rot[id],x-1,p,q);split(q,x,q,r);
	q=merge(tr[q].ls,tr[q].rs);
	rot[id]=merge(merge(p,q),r);
}
int get_num(int pos,int x){
	int u=tr[tr[pos].ls].sz;
	if(x==u+1)return tr[pos].key;
	else if(x<=u)return get_num(tr[pos].ls,x);
	else return get_num(tr[pos].rs,x-u-1);
}
int pre(int id,int x){
	int p=0,q=0,res=0;
	split(rot[id],x-1,p,q);
	if(tr[p].sz>0)res=get_num(p,tr[p].sz);
	else res=0;
	rot[id]=merge(p,q);
	return res;
}
int suf(int id,int x){
	int p=0,q=0,res=0;
	split(rot[id],x,p,q);
	if(tr[q].sz>0)res=get_num(q,1);
	else res=0;
	rot[id]=merge(p,q);
	return res;
}
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
int la[500005];
struct node{
	int vin,vax,lm;
}v[2000005];
void push_u(int rt){
	v[rt].vin=min(v[ls].vin,v[rs].vin);
	v[rt].vax=max(v[ls].vax,v[rs].vax);
	v[rt].lm=max(v[ls].lm,v[rs].lm);
}
void build(int rt,int l,int r){
	if(l==r){
		v[rt].lm=la[l];v[rt].vax=v[rt].vin=a[l];
		return ;
	}
	build(ls,l,mid);build(rs,mid+1,r);
	push_u(rt);
}
void update_lm(int rt,int l,int r,int q,int x){
	if(l==r){
		v[q].lm=x;
		return ;
	}else if(q>r || q<l)return ;
	update_lm(ls,l,mid,q,x);update_lm(rs,mid+1,r,q,x);
	push_u(rt);
}
void update_vin(int rt,int l,int r,int q,int x){
	if(l==r){
		v[q].vin=x;
		return ;
	}else if(q>r || q<l)return ;
	update_vin(ls,l,mid,q,x);update_vin(rs,mid+1,r,q,x);
	push_u(rt);
}
void update_vax(int rt,int l,int r,int q,int x){
	if(l==r){
		v[q].vax=x;
		return ;
	}else if(q>r || q<l)return ;
	update_vax(ls,l,mid,q,x);update_vax(rs,mid+1,r,q,x);
	push_u(rt);
}
int query_lm(int rt,int l,int r,int ql,int qr){
	if(ql<=l && qr>=r)return v[rt].lm;
	else if(qr<l || ql>r)return 0;
	return max(query_lm(ls,l,mid,ql,qr),query_lm(rs,mid+1,r,ql,qr));
}
int query_vin(int rt,int l,int r,int ql,int qr){
	if(ql<=l && qr>=r)return v[rt].vin;
	else if(qr<l || ql>r)return 1000000000;
	return min(query_vin(ls,l,mid,ql,qr),query_vin(rs,mid+1,r,ql,qr));
}
int query_vax(int rt,int l,int r,int ql,int qr){
	if(ql<=l && qr>=r)return v[rt].vax;
	else if(qr<l || ql>r)return 0;
	return max(query_vax(ls,l,mid,ql,qr),query_vax(rs,mid+1,r,ql,qr));
}
#undef ls
#undef rs
#undef mid
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		la[a[i]]=p[a[i]];
		p[a[i]]=i;
	}
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,l,r;scanf("%d%d%d",&op,&l,&r);
		if(op==1){
			update_vin(1,1,n,l,r);
			update_vax(1,1,n,l,r);
			int idx=p[a[l]],pr=pre(idx,l),su=suf(idx,l);del(idx,a[l]);
			la[su]=pr;a[l]=r;
			update_lm(1,1,n,su,pr);
			if(!p[r])p[r]=++cnt;
			idx=p[r];
			if(!rot[idx]){
				rot[idx]=get(r);
				pr=su=0;
			}else{
				pr=pre(idx,l);su=suf(idx,l);
				insert(idx,r);
			}
			la[l]=pr;la[su]=l;
			update_lm(1,1,n,l,pr);
			update_lm(1,1,n,su,l);
		}else{
			if(query_vax(1,1,n,l,r)-query_vin(1,1,n,l,r)==r-l && query_lm(1,1,n,l,r)<l)puts("damushen");
			else puts("yuanxing");
		}
	}
	return 0;
}

RE on 4~6

AC on 11

其余WA