题目传送门
判断一个等差数列需要三个条件，首项末项和公差。
转化一下就是最大值减去最小值是公差的长度减一倍。
并且除非公差为零否则互不相同，相邻两个位置的差的最大公约数为公差。
把这三个条件在线段树上维护并判断即可。
#include #include #include #include using namespace std; const int N=300011; mapuk; setK[N<<1]; set::iterator it; int w[N<<2],mn[N<<2],mx[N<<2],Mx[N<<2],a[N],tot,pre[N],n,m,_mx,_mn,_Mx; int iut(){ int ans=0,f=1; char c=getchar(); while (!isdigit(c)) f=(c=='-')?-f:f,c=getchar(); while (isdigit(c)) ans=ans*10+c-48,c=getchar(); return ans*f; } int min(int a,int b){return ab?a:b;} int Abs(int x){return x<0?-x:x;} int gcd(int x,int y){return y?gcd(y,x%y):x;} void pup(int k){ w[k]=gcd(w[k<<1],w[k<<1|1]); mn[k]=min(mn[k<<1],mn[k<<1|1]); mx[k]=max(mx[k<<1],mx[k<<1|1]); Mx[k]=max(Mx[k<<1],Mx[k<<1|1]); } void build(int k,int l,int r){ if (l==r){ w[k]=Abs(a[l]-a[l+1]); Mx[k]=pre[l],mx[k]=mn[k]=a[l]; return; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); pup(k); } void update(int k,int l,int r,int x){ if (l==r){ w[k]=Abs(a[l]-a[l+1]); Mx[k]=pre[l],mx[k]=mn[k]=a[l]; return; } int mid=(l+r)>>1; if (x<=mid) update(k<<1,l,mid,x); else update(k<<1|1,mid+1,r,x); pup(k); } void update0(int k,int l,int r,int x,int y){ if (l==r){ Mx[k]=y; return; } int mid=(l+r)>>1; if (x<=mid) update0(k<<1,l,mid,x,y); else update0(k<<1|1,mid+1,r,x,y); Mx[k]=max(Mx[k<<1],Mx[k<<1|1]); } void update1(int k,int l,int r,int x,int y){ if (l==r){ w[k]=Abs(y); return; } int mid=(l+r)>>1; if (x<=mid) update1(k<<1,l,mid,x,y); else update1(k<<1|1,mid+1,r,x,y); w[k]=gcd(w[k<<1],w[k<<1|1]); } int query_gcd(int k,int l,int r,int x,int y){ if (l==x&&r==y) return w[k]; int mid=(l+r)>>1; if (y<=mid) return query_gcd(k<<1,l,mid,x,y); else if (x>mid) return query_gcd(k<<1|1,mid+1,r,x,y); else return gcd(query_gcd(k<<1,l,mid,x,mid),query_gcd(k<<1|1,mid+1,r,mid+1,y)); } void query(int k,int l,int r,int x,int y){ if (l==x&&r==y){ _Mx=max(_Mx,Mx[k]); _mx=max(_mx,mx[k]); _mn=min(_mn,mn[k]); return; } int mid=(l+r)>>1; if (y<=mid) query(k<<1,l,mid,x,y); else if (x>mid) query(k<<1|1,mid+1,r,x,y); else query(k<<1,l,mid,x,mid),query(k<<1|1,mid+1,r,mid+1,y); } int main(){ n=iut(); m=iut(); for (int i=1,t;i<=n;++i){ a[i]=iut(); if (!uk[a[i]]){ uk[a[i]]=t=++tot; K[tot].insert(0); }else t=uk[a[i]]; it=--K[t].upper_bound(i); pre[i]=*it,K[t].insert(i); } build(1,1,n); for (int i=1,lans=0,t;i<=m;++i){ int opt=iut(),x=iut()^lans,y=iut()^lans; if (opt==1){ if (a[x]==y) continue; t=uk[a[x]]; K[t].erase(x); it=K[t].upper_bound(x); if (it!=K[t].end()){ int now=*it; update0(1,1,n,now,pre[now]=*(--it)); } if (x>1) update1(1,1,n,x-1,a[x-1]-y); if (!uk[y]){ uk[y]=t=++tot,K[tot].insert(pre[x]=0); }else{ t=uk[y]; it=K[t].upper_bound(x); if (it!=K[t].end()){ int now=*it; update0(1,1,n,now,pre[now]=x); } pre[x]=*(--it); } K[t].insert(x),a[x]=y; update(1,1,n,x); }else{ int z=iut()^lans; if (x==y){ ++lans,puts("Yes"); continue; } _Mx=_mx=0,_mn=0x3f3f3f3f,query(1,1,n,x,y); if ((_Mx>=x&&z)||_mx-_mn!=1ll*(y-x)*z) {puts("No"); continue;} if (query_gcd(1,1,n,x,y-1)==z) ++lans,puts("Yes"); else puts("No"); } } return 0; }