题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4373
能形成公差为k的等差数列的条件：mx-mn=k*(r-l) && 差分数组gcd为k && 区间内没有重复的数。
这些都可以线段树维护。
那个“没有重复的数”需要给每个位置记下权值的pre，修改的时候需要找到它前面一个和后面一个。
用链表的话没法插入。可以给每个权值开一个set，就能用lower_bound了。
有些细节。重载运算符很方便。
#include<iostream> #include<cstdio> #include<cstring> #include<map> #include<set> using namespace std; const int N=3e5+5,INF=1e9+5; int n,m,c[N],ls[N<<1],rs[N<<1],tot,pre[N],lt,cnt; map<int,int> mp; set<int> s[N<<1]; int gcd(int a,int b){return b?gcd(b,a%b):a;} int abss(int k){return k<0?-k:k;} struct Node{ int mx,mn,lst,g; Node(int a=0,int b=0,int l=0,int g=0):mx(a),mn(b),lst(l),g(g) {} Node operator+ (const Node &b)const { return Node(max(mx,b.mx),min(mn,b.mn),max(lst,b.lst),gcd(g,b.g)); } }a[N<<1]; void add(int x) { mp[x]=++cnt;s[cnt].insert(0);s[cnt].insert(n+1); } void pshp(int cr) { a[cr]=a[ls[cr]]+a[rs[cr]]; } void build(int l,int r,int cr) { if(l==r) { a[cr]=Node(c[l],c[l],pre[l],abss(c[l+1]-c[l]));return; } int mid=((l+r)>>1); ls[cr]=++tot;build(l,mid,ls[cr]); rs[cr]=++tot;build(mid+1,r,rs[cr]); pshp(cr);//!!! } void updt(int l,int r,int cr,int p) { if(l==r) { a[cr]=Node(c[l],c[l],pre[l],abss(c[l+1]-c[l]));return; } int mid=((l+r)>>1); if(p<=mid)updt(l,mid,ls[cr],p); else updt(mid+1,r,rs[cr],p); pshp(cr); } Node query(int l,int r,int cr,int L,int R) { if(l>=L&&r<=R)return a[cr]; int mid=((l+r)>>1); if(L>mid)return query(mid+1,r,rs[cr],L,R); if(R<=mid)return query(l,mid,ls[cr],L,R); return query(l,mid,ls[cr],L,R)+query(mid+1,r,rs[cr],L,R); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&c[i]); if(!mp[c[i]])add(c[i]); int t=mp[c[i]]; pre[i]=*--s[t].lower_bound(i); s[t].insert(i); } a[n+1]=a[n];//?是为了让最后一个点的差分是0，使不影响吧 tot=1;build(1,n,1); int op,x,y; while(m--) { scanf("%d",&op); if(op==1) { scanf("%d%d",&x,&y);x^=lt;y^=lt; int t=mp[c[x]]; int u=*--s[t].lower_bound(x),v=*s[t].upper_bound(x); if(v!=n+1)pre[v]=u,updt(1,n,1,v);//v!=n+1 s[t].erase(x); if(!mp[y])add(y);t=mp[y]; u=*--s[t].lower_bound(x);v=*s[t].upper_bound(x); if(v!=n+1)pre[v]=x,updt(1,n,1,v);//v!=n+1 pre[x]=u;c[x]=y;s[t].insert(x); updt(1,n,1,x); if(x!=1)updt(1,n,1,x-1);//x!=1//为了改差分 } else { int L,R,k; scanf("%d%d%d",&L,&R,&k);L^=lt;R^=lt;k^=lt; if(L==R){printf("Yes ");lt++;continue;}//放在下面那个if的上面！ Node ans0=query(1,n,1,L,R-1),ans=ans0+query(1,n,1,R,R);//为了差分弄ans0 if(!k) //放在下面那个if的上面！ { if(ans.mx==ans.mn)printf("Yes "),lt++; else printf("No "); continue; } if(ans.lst<L&&ans.mx-ans.mn==k*(R-L)&&ans0.g==k)printf("Yes "),lt++; else printf("No "); } } return 0; }