题目大意：
一个长度为n的序列，其中第i个数为a[i]。修改一个点的值询问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。
思路：
1.一段区间符合要求满足：(1)区间中的max-min=(r-l)*公差;(2)区间相邻的两个数的差的gcd为公差;(3)区间内的数不重复。 2.(1)(2)用一个线段树维护，(3)首先，序列出现过的值最多只有600000种，所以可以对于每个值开一个set（离散化），对应的id用一个map存起来。然后维护一个pre[i]，表示当前a[i]这个值，在i前面最后一次出现的位置。那么满足(3)，当且仅当区间[l,r]的pre的最大值小于l。这个也是用线段树维护。然后看修改操作：在set上找前一个数、后一个数，然后修改相应的值。
反思：
(1)(2)比较好求就打了，网上有人这样A了，(3)既不理解又不会STL就不打了（逃…… 单点时公差可为任何数，要特判。线段树修改时从底向上更新，gcd原来与最大最小值分开和加法一样打的，可WA了就换成这样了（不过原来的应该是能A的）。
代码：
1 #include<cstdio> 2 const int M=300005; 3 struct data{ int l,r,max,min,gcd; }t[M<<2],u,v; 4 int p,a[M]; 5 6 int abs(int x) { return x>0?x:-x; } 7 int Min(int x,int y) { return x<y?x:y; } 8 int Max(int x,int y) { return x>y?x:y; } 9 10 int read() 11 { 12 int x=0; char ch=getchar(); 13 for (;ch<48 || ch>57;ch=getchar()); 14 for (;ch>47 && ch<58;ch=getchar()) x=(x<<1)+(x<<3)+ch-48; 15 return x; 16 } 17 18 int Gcd(int x,int y) 19 { 20 if (!x) return y; if (!y) return x; 21 for (int z;y;z=y,y=x%z,x=z); 22 return x; 23 } 24 25 void push_up(int k) 26 { 27 t[k].l=t[k<<1].l,t[k].r=t[k<<1|1].r; 28 t[k].max=Max(t[k<<1].max,t[k<<1|1].max); 29 t[k].min=Min(t[k<<1].min,t[k<<1|1].min); 30 t[k].gcd=Gcd(Gcd(t[k<<1].gcd,t[k<<1|1].gcd),abs(t[k<<1].r-t[k<<1|1].l)); 31 } 32 33 void build(int l,int r,int k) 34 { 35 if (l==r) { t[k].max=t[k].min=t[k].l=t[k].r=a[l]; return; } 36 int mid=l+r>>1; build(l,mid,k<<1),build(mid+1,r,k<<1|1),push_up(k); 37 } 38 39 void change(int l,int r,int k,int x,int cur) 40 { 41 if (l==r) { t[cur].max=t[cur].min=t[cur].l=t[cur].r=x; return; } 42 int mid=l+r>>1; 43 if (k>mid) change(mid+1,r,k,x,cur<<1|1); 44 else change(l,mid,k,x,cur<<1); 45 push_up(cur); 46 } 47 48 data query(int l,int r,int L,int R,int cur) 49 { 50 if (L<=l && r<=R) return t[cur]; 51 int mid=l+r>>1; data x,y,z=v; 52 bool fl=0,fr=0; 53 if (L<=mid) fl=1,x=query(l,mid,L,R,cur<<1); 54 if (R>mid) fr=1,y=query(mid+1,r,L,R,cur<<1|1); 55 if (fl) 56 if (fr) z.l=x.l,z.r=y.r,z.max=Max(x.max,y.max), 57 z.min=Min(x.min,y.min),z.gcd=Gcd(Gcd(x.gcd,y.gcd),abs(x.r-y.l)); 58 else z=x; 59 else z=y; 60 return z; 61 } 62 63 int main() 64 { 65 int n=read(),m=read(),x,y,k,i; 66 for (i=1;i<=n;++i) a[i]=read(); 67 for (build(1,n,1);m--;) 68 if (read()^2) x=read()^p,y=read()^p,change(1,n,x,y,1); 69 else 70 { 71 x=read()^p,y=read()^p,k=read()^p,u=query(1,n,x,y,1); 72 if (x==y || u.gcd==k && u.max-u.min==(y-x)*k) puts("Yes"),++p; 73 else puts("No"); 74 } 75 return 0; 76 }
转载于:https://www.cnblogs.com/HHshy/p/7189694.html
相关资源：JAVA上百实例源码以及开源项目