本文共 3304 字，大约阅读时间需要 11 分钟。
看上去很难维护，考虑找一些必要条件。首先显然最大值-最小值=k*(r-l)。然后区间内的数需要模k同余。最后区间内的数两两不同（k=0除外）。冷静一下可以发现这些条件组合起来就是充分的了。
考虑怎么维护。最大值最小值非常简单。模k同余相当于区间内相邻两数的差都是k的倍数，可以维护差分数组的gcd。两两不同相当于区间内没有出现次数>1的数，对每个数用set维护上一个和他相同的数的位置，线段树维护，区间查询max，如果<l则说明不存在。
开始判断是否不同的写出锅了，结果删掉竟然过了23333
#include #include #include #include #include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 300010#define ll long longint n,m,a[N],b[N],lst,cnt;map f;set pre[N<<1];int L[N<<2],R[N<<2],mn[N<<2],mx[N<<2],GCD[N<<2],last[N<<2];int gcd(int n,int m){ return m==0?n:gcd(m,n%m);}void up(int k){ mn[k]=min(mn[k<<1],mn[k<<1|1]); mx[k]=max(mx[k<<1],mx[k<<1|1]); last[k]=max(last[k<<1],last[k<<1|1]); GCD[k]=gcd(GCD[k<<1],GCD[k<<1|1]);}void build(int k,int l,int r){ L[k]=l,R[k]=r; if (l==r) { mn[k]=mx[k]=a[l];GCD[k]=b[l]; last[k]=*(--pre[f[a[l]]].find(l)); return; } int mid=l+r>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); up(k);}void modify(int k,int p,int x,int op){ if (L[k]==R[k]) { if (op==0) mn[k]=mx[k]=x; else if (op==1) GCD[k]=x; else last[k]=x; return; } int mid=L[k]+R[k]>>1; if (p<=mid) modify(k<<1,p,x,op); else modify(k<<1|1,p,x,op); up(k);}int qmax(int k,int l,int r){ if (L[k]==l&&R[k]==r) return mx[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return qmax(k<<1,l,r); else if (l>mid) return qmax(k<<1|1,l,r); else return max(qmax(k<<1,l,mid),qmax(k<<1|1,mid+1,r)); }int qmin(int k,int l,int r){ if (L[k]==l&&R[k]==r) return mn[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return qmin(k<<1,l,r); else if (l>mid) return qmin(k<<1|1,l,r); else return min(qmin(k<<1,l,mid),qmin(k<<1|1,mid+1,r)); }int qgcd(int k,int l,int r){ if (L[k]==l&&R[k]==r) return GCD[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return qgcd(k<<1,l,r); else if (l>mid) return qgcd(k<<1|1,l,r); else return gcd(qgcd(k<<1,l,mid),qgcd(k<<1|1,mid+1,r)); }int qlast(int k,int l,int r){ if (L[k]==l&&R[k]==r) return last[k]; int mid=L[k]+R[k]>>1; if (r<=mid) return qlast(k<<1,l,r); else if (l>mid) return qlast(k<<1|1,l,r); else return max(qlast(k<<1,l,mid),qlast(k<<1|1,mid+1,r)); }int main(){#ifndef ONLINE_JUDGE freopen("1.in","r",stdin); freopen("bzoj4373.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(); for (int i=1;i<=n;i++) { a[i]=read(),b[i]=abs(a[i]-a[i-1]); if (f.find(a[i])==f.end()) f[a[i]]=++cnt,pre[cnt].insert(0); pre[f[a[i]]].insert(i); } build(1,1,n); while (m--) { int op=read(); if (op==1) { int p=read()^lst,x=read()^lst; int t=f[a[p]];set ::iterator it=++pre[t].find(p); if (it!=pre[t].end()) modify(1,*it,*(--pre[t].find(p)),2); pre[t].erase(p); a[p]=x;modify(1,p,x,0); modify(1,p,abs(a[p]-a[p-1]),1); if (p<=n) modify(1,p+1,abs(a[p+1]-a[p]),1); if (f.find(a[p])==f.end()) f[a[p]]=++cnt,pre[cnt].insert(0); t=f[a[p]];it=pre[t].lower_bound(p); if (it!=pre[t].end()) modify(1,*it,p,2); it--;modify(1,p,*it,2);pre[t].insert(p); } else { int l=read()^lst,r=read()^lst,d=read()^lst; if (qmax(1,l,r)-qmin(1,l,r)==1ll*d*(r-l)&&(d==0||l==r||((qgcd(1,l+1,r)%d==0)&&qlast(1,l,r)
转载于:https://www.cnblogs.com/Gloid/p/9866430.html