题解：P5278 算术天才⑨与等差数列

114514xxx · 2025-08-10 20:29:44 · 题解

考虑对于数列 \{a_n\} 如何判别为等差数列。暴力排序单次时间复杂度就来到了 O(n \log n)，太慢了，我们需要更快的方法。

先考虑 k=0 的情况。仅需 \displaystyle\max^{n}_{i=1}a_i=\min^{n}_{i=1}a_i 即可。

接下来考虑 k > 0 的情况。首先 \displaystyle\max^{n}_{i=1}a_i-\min^{n}_{i=1}a_i =(n-1)k。我们发现这仅仅是一个充分不必要条件，因此我们还要更多的条件。注意到任意的 a_i 都可以表示为 a_i=\min^{n}_{i=1}a_i + mk，其中 0\le m \le n-1，且 m 为整数。进一步讲就是所有的 a_i 对 k 是同余的。并且所有 a_i 也都是互异的。

于是我们尝试维护，但发现所有的 a_i 对 k 是同余的是不好维护的，因此我们转用数列 \{a_n\} 的差分数列 \{d_n\} 进行维护，根据上面结论我们知道了所有 d_i 都是 k 的倍数。因此只要 \gcd(d_1,d_2,\ldots,d_n)=k 就代表有的 a_i 对 k 是同余的了。

如何维护所有数互异呢，set 套 map 后放到线段树上即可。

总结得到以下条件：

1. \displaystyle\max^{n}_{i=1}a_i-\min^{n}_{i=1}a_i =(n-1)k
2. 设 d_i=a_i-a_{i-1}，且 \gcd(d_1,d_2,\ldots,d_n)=k
3. 所有数互异

上面这些条件线段树维护就可以了，时间复杂度 O(n \log^2 n)。两个 \log 分别来自线段树和 \gcd。

放下代码。

#include<bits/stdc++.h>
#define ls p*2
#define rs p*2+1
using namespace std;
const int N=3e5+25;
const int inf=2e9;
char *p1,*p2,buf[1<<21];
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
#define readin(fn) FILE *fin = freopen(#fn ".in", "r", stdin)
#define output(fn) FILE *fout = freopen(#fn ".out", "w", stdout)
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<48|ch>57){
        ch=getchar();
        if(ch=='-')f*=-1;
    }
    while(ch>=48&&ch<=57)
        x=(x*10)+(ch^48),ch=getchar();
    return x*f;
}
int gcd(int a, int b) {
    if(!a||!b)return a+b;
    int az=__builtin_ctz(a);
    int bz=__builtin_ctz(b);
    int z=min(az,bz);
    b>>=bz;
    int diff=0;
    while (a){
        a>>=az;
        diff=a-b;
        az=__builtin_ctz(diff);
        b=min(a,b),a=abs(diff);
    }
    return b<<z;
}//Binary GCD，比一般 GCD 更快一些
struct SegmentTree1{
    struct node{
        int l,r,maxn,minn;
    }t[N<<2];
    inline void update(int p){
        t[p].maxn=max(t[ls].maxn,t[rs].maxn);
        t[p].minn=min(t[ls].minn,t[rs].minn);
    }
    inline void build(int p,int l,int r,int *a){
        t[p].l=l,t[p].r=r;
        if(l==r){
            t[p].maxn=a[l];t[p].minn=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid,a);
        build(rs,mid+1,r,a);
        update(p);
    }
    inline void modify(int p,int x,int k){
        if(t[p].l==t[p].r&&t[p].l==x){
            t[p].maxn=t[p].minn=k;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(x<=mid)modify(ls,x,k);
        if(x>mid)modify(rs,x,k);
        update(p);
    }
    inline int query_max(int p,int l,int r){
        if(t[p].l>=l&&t[p].r<=r)return t[p].maxn;
        int ans=0;
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid)ans=max(ans,query_max(ls,l,r));
        if(r>mid)ans=max(ans,query_max(rs,l,r));
        return ans;
    }
    inline int query_min(int p,int l,int r){
        if(t[p].l>=l&&t[p].r<=r)return t[p].minn;
        int ans=inf;
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid)ans=min(ans,query_min(ls,l,r));
        if(r>mid)ans=min(ans,query_min(rs,l,r));
        return ans;
    }   
}t1,t2;
struct GcdTree{
    struct node{
        int l,r,val;
    }t[N<<2];
    inline void update(int p){t[p].val=gcd(t[ls].val,t[rs].val);}
    inline void build(int p,int l,int r,int *a){
        t[p].l=l,t[p].r=r;
        if(l==r){t[p].val=a[l];return;}
        int mid=(l+r)>>1;
        build(ls,l,mid,a);
        build(rs,mid+1,r,a);
        update(p);
    }
    inline void modify(int p,int x,int k){
        if(t[p].l==t[p].r&&t[p].l==x){
            t[p].val=k;
            return;
        }
        int mid=(t[p].l+t[p].r)>>1;
        if(x<=mid)modify(ls,x,k);
        if(x>mid)modify(rs,x,k);
        update(p);
    }
    inline int query(int p,int l,int r){
        if(t[p].l>=l&&t[p].r<=r)return t[p].val;
        int mid=(t[p].l+t[p].r)>>1,ans=0;
        if(l<=mid)ans=gcd(ans,query(ls,l,r));
        if(r>mid)ans=gcd(ans,query(rs,l,r));
        return ans;
    }
}gcdt;
set<int>s[N<<1];
unordered_map<int,int>mp;
int n,m,a[N],d[N];
int pre[N],suf[N];
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)d[i]=abs(a[i]-a[i-1]);
    t1.build(1,1,n,a);
    gcdt.build(1,1,n,d);
    int idx=0;
    for(int i=1;i<=n;i++){
        if(!mp.count(a[i]))mp[a[i]]=++idx;
        auto it=s[mp[a[i]]].end();
        if(it!=s[mp[a[i]]].begin())--it,pre[i]=*it,suf[*it]=i;
        s[mp[a[i]]].insert(i);
    }
    t2.build(1,1,n,pre);
    int op,x,y,l,r,k;
    int lastans=0;
    while(m--){
         op=read();
        if(op==1){
            x=read(),y=read();
            x^=lastans,y^=lastans;
            if(a[x]==y)continue;
            s[mp[a[x]]].erase(x);
            a[x]=y;
            d[x]=a[x]-a[x-1];
            d[x+1]=a[x+1]-a[x];
            d[x]=abs(d[x]),d[x+1]=abs(d[x+1]);
            int tmp1=suf[x];
            if(pre[x])suf[pre[x]]=suf[x];
            if(suf[x])pre[suf[x]]=pre[x];
            t2.modify(1,tmp1,pre[suf[x]]);
            t1.modify(1,x,a[x]);
            gcdt.modify(1,x,d[x]);
            if(x<n)gcdt.modify(1,x+1,d[x+1]);
            if(!mp.count(y))mp[y]=++idx;
            if(s[mp[y]].size()>0){
                auto it=s[mp[y]].lower_bound(x);
                if(it==s[mp[y]].end()){
                    suf[x]=0;
                    if(it!=s[mp[y]].begin()){
                        --it;
                        pre[x]=*it;
                        suf[*it]=x;
                    }else pre[x]=0;
                }else{
                    suf[pre[*it]]=x,pre[x]=pre[*it];
                    suf[x]=*it,pre[*it]=x;
                    t2.modify(1,*it,pre[*it]);
                    t2.modify(1,suf[x],x);
                }
            }else pre[x]=suf[x]=0;
            s[mp[y]].insert(x);
            t2.modify(1,x,pre[x]);
        }else{
            l=read(),r=read(),k=read();
            l^=lastans,r^=lastans,k^=lastans;
            if(l>r)continue;
            int maxf=t1.query_max(1,l,r);
            int minf=t1.query_min(1,l,r);
            if(k==0&&maxf==minf){cout<<"Yes\n",++lastans;continue;}
            if(l==r){cout<<"Yes\n",++lastans;continue;}
            int val=gcdt.query(1,l+1,r);
            if(val!=k){cout<<"No\n";continue;}
            if((long long)(maxf-minf)!=(long long)((r-l)*k)){cout<<"No\n";continue;}
            int pref=t2.query_max(1,l,r);
            //cout<<maxf<<' '<<minf<<' '<<val<<' '<<pref<<'\n';
            if(pref>=l){cout<<"No\n";continue;}
            if((long long)(maxf-minf)==(long long)((r-l)*k)&&pref<l)
                cout<<"Yes\n",++lastans;
            else cout<<"No\n";
        }
    }
}