[文章目录]
Description
有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。n,m(1<=n,m<=300000).
他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。n,m(1<=n,m<=300000).
大师讲的题目，好难。也收获颇丰啊。
一个数列是等差数列当且仅当：
1.数列中的最大值-最小值=（公差*个数-1）
2.数列中的每两个数的差都为公差的倍数
3.数列中没有重复的数字
（需要特判数列中只有一个元素和公差为0的情况）
第一个条件线段树就好了。
第二个条件想到只要任意两个相邻的数之间的差能整除公差就行，另外gcd是符合区间加法的，所以我们维护一个差分数组的gcd。
第三个条件，维护每一位上的数在其之前与其最近的相等的数的位置，记为pre[i]，所以只要是区间里的pre[i]的最大值小于l，就说明所有的数没有相同的，线段树搞一下。不过pre{i]怎么求？？？，我们需要维护一个set，优先级为先按值排序，后按位置由小到大排序，每次二分查找，修改就好了。
STL是个好东西。
NOTE:
区间判断没有重复的数：set+seg维护pre[i]。
区间gcd：是符合区间加法的
题目的划归与转化。（想不出来啊）
代码里加了点set的用法，支持结构体，优先级需要重载运算符。
set:插入log(n)后自动排序，log(n)查询的数据结构：
1.提供iterator，是个结构体指针，支持++，--；
2.upper_bound (node )返回迭代器，指向优先级大于node的第一个元素
3.lower_bound (node )返回迭代器，指向优先级大于等于node的第一个元素
4.insert (node ) 插入node
5.erase(node ) 清除node
6.#include <set>
set <node> 不重集合
multiset <node>可重集合
#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 301000
int n,m,M,sol;
int mx[N<<2],mi[N<<2],g[N<<2],mxpre[N<<2];
int a[N],op;
struct node {int pos,key;};
bool operator < (node x,node y) {return x.key==y.key ? x.pos<y.pos : x.key<y.key;}
multiset <node> s;
multiset <node>::iterator it;
int read()
{
char ch=getchar();int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
int gcd(int x,int y) {return (y==0) ? x:gcd(y,x%y);}
inline int Abs(int x) {return x>0 ? x : -x;}
void pushup(int x)
{
mx[x]=max(mx[x<<1],mx[x<<1|1]);
mi[x]=min(mi[x<<1],mi[x<<1|1]);
g[x]=gcd(g[x<<1],g[x<<1|1]);
mxpre[x]=max(mxpre[x<<1],mxpre[x<<1|1]);
}
void query_tree(int l,int r,int &mxx,int &mii,int &prex)
{
prex=mxx=-1<<30;mii=1<<30;
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1)
{
mxx=max(mxx,mx[l^1]);mii=min(mii,mi[l^1]);
prex=max(prex,mxpre[l^1]);
}
if(r&1)
{
mxx=max(mxx,mx[r^1]);mii=min(mii,mi[r^1]);
prex=max(prex,mxpre[r^1]);
}
}
}
int query_gcd(int l,int r)
{
int re=-1;
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) re= ((re==-1) ? g[l^1]:gcd(g[l^1],re));
if(r&1) re= ((re==-1) ?g[r^1]:gcd(g[r^1],re));
}
return re;
}
void fix()
{
int x,y,val; x=read();val=read(); x^=sol,val^=sol;
it=s.upper_bound((node){x,a[x]});
if(it!=s.end() && it->key==a[x])
{
mxpre[it->pos+M]=mxpre[x+M];
y=it->pos+M; while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
}
s.erase((node){x,a[x]}); a[x]=val; s.insert((node){x,a[x]});
it=s.upper_bound((node){x,a[x]});
if(it!=s.end() && it->key==a[x])
{
mxpre[it->pos+M]=x; y=it->pos+M;
while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
}
it=s.lower_bound((node){x,a[x]});
mxpre[x+M]= (it!=s.begin()&&(it--,it->key==a[x])) ? it->pos : 0;
y=x+M; while(y>>=1) mxpre[y]=max(mxpre[y<<1],mxpre[y<<1|1]);
x+=M; g[x]=Abs(val-a[x-M-1]); mx[x]=mi[x]=val; y=x;
while(y>>=1) pushup(y);
if(x!=n+M)
{
y=x+1; g[y]=Abs(a[y-M]-a[x-M]);
while(y>>=1) g[y]=gcd(g[y<<1],g[y<<1|1]);
}
}
void build()
{
for(M=1;M<n+2;M<<=1);
for(int i=M+1;i<=M+n;i++)
{
a[i-M]=read(); s.insert((node){i-M,a[i-M]}); it=s.lower_bound((node){i-M,a[i-M]}); it--;
if(it!=s.begin() && it->key==a[i-M] ) mxpre[i]=it->pos;
mx[i]=mi[i]=a[i-M];
g[i]=Abs(a[i-M]-a[i-M-1]);
}
for(int i=M-1;i;i--) pushup(i);
}
void query()
{
int l,r,k;l=read();r=read();k=read();l^=sol,r^=sol,k^=sol;
if(l==r) {puts("Yes"); sol++; return ;}
if(l>r) {puts("No"); return ;}
int mxx,mii,prex;
query_tree(l,r,mxx,mii,prex);
if(k==0)
{
if(mxx==mii) puts("Yes"),sol++;
else puts("No");
return ;
}
if((mxx-mii)!=(r-l)*k) {puts("No");return ;}
if(prex>=l) {puts("No");return ;}
if(query_gcd(l+1,r)!=k){puts("No");return ;}
puts("Yes"); sol++; return ;
}
int main()
{
scanf("%d%d",&n,&m);
build();
while(m--)
{
op=read();
switch(op)
{
case 1: fix();break;
case 2: query();break;
}
}
return 0;
}