题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4373
一个区间有以 k 为公差的数列，有3个条件：
1.区间 mx - mn = (r-l) * k；
2.差分数组的 gcd 是 k 的倍数；
3.没有重复出现的数；
其中1,2都可以用线段树维护，3用 set 维护每个数上一个出现的位置即可；
模仿TJ写的：https://blog.csdn.net/neither_nor/article/details/52461940
对 set 更熟悉了，细节还蛮多的。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<map>
using namespace std;
int const maxn=3e5+;
int n,m,a[maxn],key,tot,pre[maxn];
map<int,int>h;
set<int>s[maxn<<];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ab(int x){return x>?x:-x;}
struct N{
int mx,mn,fro,g;
friend N operator + (N x,N y)
{
N ret;
ret.mx=max(x.mx,y.mx);
ret.mn=min(x.mn,y.mn);
ret.fro=max(x.fro,y.fro);
ret.g=gcd(x.g,y.g);
return ret;//!
}
}t[maxn<<];
void build(int x,int l,int r)
{
if(l==r)
{
t[x].mn=t[x].mx=a[l]; t[x].g=ab(a[l+]-a[l]);
t[x].fro=pre[l]; return;
}
int mid=((l+r)>>);
build(x<<,l,mid); build(x<<|,mid+,r);
t[x]=t[x<<]+t[x<<|];
}
void update(int x,int l,int r,int p)
{
if(l==r)
{
t[x].mn=t[x].mx=a[l]; t[x].g=ab(a[l+]-a[l]);
t[x].fro=pre[l]; return;
}
int mid=((l+r)>>);
if(p<=mid)update(x<<,l,mid,p);
else update(x<<|,mid+,r,p);
t[x]=t[x<<]+t[x<<|];
}
N query(int x,int l,int r,int L,int R)
{
if(l>=L&&r<=R)return t[x];
int mid=((l+r)>>);
if(mid<L)return query(x<<|,mid+,r,L,R);
else if(mid>=R)return query(x<<,l,mid,L,R);
else return query(x<<,l,mid,L,R)+query(x<<|,mid+,r,L,R);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(!h[a[i]])
{
h[a[i]]=++tot;
s[tot].insert();
s[tot].insert(n+);
}
int tmp=h[a[i]];
s[tmp].insert(i);
pre[i]=*--(s[tmp].insert(i).first);//
}
a[n+]=a[n];//!
build(,,n);
for(int i=,op,x,y,l,r,k;i<=m;i++)
{
scanf("%d",&op);
if(op==)
{
scanf("%d%d",&x,&y);
x^=key; y^=key;
int tmp,nxt,pr;
tmp=h[a[x]];
nxt=*s[tmp].upper_bound(x);
if(nxt!=n+)
{
pre[nxt]=pre[x];
update(,,n,nxt);
}
s[tmp].erase(x); if(!h[y])//
{
h[y]=++tot;
s[tot].insert();
s[tot].insert(n+);
}
tmp=h[y];
s[tmp].insert(x);
nxt=*s[tmp].upper_bound(x);
pre[x]=*--s[tmp].lower_bound(x);
if(nxt!=n+)
{
pre[nxt]=x;
update(,,n,nxt);
}
a[x]=y;
update(,,n,x);
if(x!=)update(,,n,x-);//
}
if(op==)
{
scanf("%d%d%d",&l,&r,&k);
l^=key; r^=key; k^=key;
if(l==r){key++; printf("Yes\n"); continue;}
N tmpp=query(,,n,l,r-);//
N tmp=tmpp+query(,,n,r,r);//
if(k==)
{
if(tmp.mx==tmp.mn)key++,printf("Yes\n");
else printf("No\n");
continue;
}
if(tmp.fro<l && tmp.mx==k*(r-l)+tmp.mn && tmpp.g%k==)//tmpp!
key++,printf("Yes\n");
else printf("No\n");
}
}
return ;
}