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

flower1 · 2025-08-07 20:00:25 · 题解

Solution

看了其他人的做法，感觉维护相邻差分的 \gcd 还是有点难想到的，于是就有了这篇暴力随机化做法。

对于一个长度为 n 的序列 a，设其最小值为 a_1，最大值为 a_n，如果它排序后能构成公差为 d 的等差数列，要满足以下几点：

2. 序列中不存在重复元素。

对于第一点，可以用线段树维护区间最大值与最小值。

对于第二点，可以求出每个元素，和它相同元素上一次出现的位置，如果区间所有元素上一次出现的位置小于左端点，那么区间中就没有重复元素。

可以采用线段树维护区间最值，用 map 离散化后套 set 动态维护。

对于第三点，一个很经典的做法就是随机化。

首先，若每个 a_i-a_1 都能整除 d ，则它们的和也一定能整除 d。

我们开 10 个树状数组维护区间和，对于序列的每个位置，树状数组都随机以 \frac{1}{2} 的概率维护这个值，如果有任意一个树状数组的区间和不能整除 d ，那么就不合法，这样做程序错误的概率很低。

时间复杂度 O(n \log^2 n)，空间复杂度 O(n \log n)，理论上难以通过，但由于数据极水可以 AC。

#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;
const int N=3e5+5,M=10;
int n,m,idx,a[N],pr[N],sf[N],ans;
map<int,int>mp;
set<int>st[N<<1];
struct node{
    int mi,mx,p,gd;
};
struct tree1{
    node tr[N<<2];
    node pushup(node x,node y,int mid){
        node k;
        k.mi=min(x.mi,y.mi);
        k.mx=max(x.mx,y.mx); 
        k.p=max(x.p,y.p);
        k.gd=__gcd(__gcd(x.gd,y.gd),abs(a[mid]-a[mid+1]));
        return k;
    }
    void build(int k,int l,int r){
        if(l==r){
            tr[k]=(node){a[l],a[l],pr[l],0};
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid),build(rs,mid+1,r);
        tr[k]=pushup(tr[ls],tr[rs],mid);
    }
    void modify(int k,int l,int r,int x){
        if(l==r){
            tr[k]=(node){a[l],a[l],pr[l],0};
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid) modify(ls,l,mid,x);
        if(mid+1<=x) modify(rs,mid+1,r,x);
        tr[k]=pushup(tr[ls],tr[rs],mid);
    }
    node query(int k,int l,int r,int x,int y){
        if(x<=l&&r<=y)
            return tr[k];
        int mid=(l+r)>>1;
        if(x<=mid&&mid+1<=y) return pushup(query(ls,l,mid,x,y),query(rs,mid+1,r,x,y),mid);
        else if(x<=mid) return query(ls,l,mid,x,y);
        else return query(rs,mid+1,r,x,y);
    }
}stk;
struct tree2{
    ll c[N];
    int d[N];
    bool vis[N];
    void build(){
        for(int i=1;i<=n;i++){
            if(rand()%2==0)
                vis[i]=true;
            add(i,a[i]);
        }
    }
    void add(int x,int v){
        if(vis[x]) return;
        for(int i=x;i<=n;i+=lowbit(i)){
            c[i]+=v;
            if(v>0) d[i]++;
            else d[i]--; 
        }
    }
    ll sum(int x){
        ll res=0;
        for(int i=x;i>=1;i-=lowbit(i))
            res+=c[i];
        return res; 
    }
    ll query(int x,int y){
        return sum(y)-sum(x-1);
    }
    int sum2(int x){
        ll res=0;
        for(int i=x;i>=1;i-=lowbit(i))
            res+=d[i];
        return res; 
    }
    int query2(int x,int y){
        return sum2(y)-sum2(x-1);
    }
}str[12];
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k; 
}
int main(){
    srand(time(NULL));
    int opt,l,r,x,y;
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(!mp.count(a[i]))
            mp[a[i]]=++idx;
        auto it=st[mp[a[i]]].end(); 
        if(it!=st[mp[a[i]]].begin()){
            it--;
            pr[i]=*it,sf[*it]=i;
        }
        st[mp[a[i]]].insert(i);
    }
    stk.build(1,1,n);
    for(int i=1;i<=M;i++)
        str[i].build();
    for(int i=1;i<=m;i++){
        opt=read();
        if(opt==1){
            x=read()^ans,y=read()^ans;
            if(a[x]==y)
                continue;
            if(pr[x]) sf[pr[x]]=sf[x];
            if(sf[x]) pr[sf[x]]=pr[x],stk.modify(1,1,n,sf[x]);
            st[mp[a[x]]].erase(x);
            if(!mp.count(y))
                mp[y]=++idx;
            if(st[mp[y]].size()>0){
                auto it=st[mp[y]].lower_bound(x);
                if(it==st[mp[y]].end()){
                    sf[x]=0;
                    if(it!=st[mp[y]].begin()){
                        it--;
                        sf[*it]=x;
                        pr[x]=*it;
                    }
                    else
                        pr[x]=0;
                }
                else{
                    sf[pr[*it]]=x,pr[x]=pr[*it];
                    sf[x]=*it,pr[*it]=x;
                    stk.modify(1,1,n,sf[x]);
                }
            }
            else
                pr[x]=0,sf[x]=0;
            for(int j=1;j<=M;j++)
                str[j].add(x,-a[x]),str[j].add(x,y);
            a[x]=y;
            stk.modify(1,1,n,x);
            st[mp[y]].insert(x);
        }
        else{
            l=read()^ans,r=read()^ans,x=read()^ans;
            node t=stk.query(1,1,n,l,r);
            if((r-l!=0)&&((x>0&&t.p>=l)||t.mx-t.mi!=(r-l)*x))
                printf("No\n");
            else if(x==0)
                printf("Yes\n"),ans++;
            else{
                int vl=0;
                for(int j=1;j<=M;j++){
                    if((str[j].query(l,r)-1ll*t.mi*str[j].query2(l,r))%x!=0){
                        vl=1;
                        break;
                    }
                }
                if(vl)
                    printf("No\n");
                else
                    printf("Yes\n"),ans++; 
            }
        }
    }
    return 0;
}