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

TheShadow · 2019-10-08 11:08:25 · 题解

闲扯

这道题 JKLover 讲过，然后补课的时候老师也提到了，想了想还是做了吧，顺便写篇题解纪念一下。

题面

P5278 算术天才⑨与等差数列

Solution

对于一个序列，如果它排序后能构成一个公差为 d 等差数列，一定满足一下几点：

序列中没有重复元素。

前两个条件很好维护，直接上线段树即可，所以我们需要着重解决的是第 3 个条件。

有一个很巧妙的方法，我们可以求出每一个元素，它在序列中上一次出现的位置，如果这一个区间中所有元素上一次出现位置的最大值小于 l ，那么一定没有重复元素。

因为数据范围很大，而且是强制在线，所以我们用 map 套 set 存一下，单点修改时注意下边界条件即可。

需要注意的是一个数的数列也算是等差数列，还有在 d=0 时我们直接判断最大值是否等于最小值即可。

Code

#include<bits/stdc++.h>
#include<unordered_map>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
    int f=1;char k=getchar();x=0;
    for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
    for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
    x*=f;
}
template<class T>il _print(T x){
    if(x/10) _print(x/10);
    putchar(x%10+'0');
}
template<class T>il print(T x){
    if(x<0) putchar('-'),x=-x;
    _print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
    int res=1,bas=x%mod;
    while(m){
        if(m&1) res=(1ll*res*bas)%mod;
        bas=(1ll*bas*bas)%mod,m>>=1;
    }
    return res%mod;
}
const int MAXN = 3e5+5;
int n,m,val[MAXN],opt,x,y,k,cnt,pre[MAXN];
unordered_map<int,set<int> > mp;
set<int>::iterator ite;
it gcd(int x,int y){return y==0?x:gcd(y,x%y);}
it max(int x,int y){return x>y?x:y;}
it min(int x,int y){return x<y?x:y;}
#define lc (cur<<1)
#define rc (cur<<1|1)
struct Seg_Tree{
    int mx,mn,mx_pre;
}T[MAXN<<2];
il pushup(int cur){
    T[cur].mn=min(T[lc].mn,T[rc].mn);
    T[cur].mx=max(T[lc].mx,T[rc].mx);
    T[cur].mx_pre=max(T[lc].mx_pre,T[rc].mx_pre);
}
il build_tree(int cur,int l,int r){
    if(l==r) return T[cur].mn=T[cur].mx=val[l],T[cur].mx_pre=pre[l],void();
    build_tree(lc,l,mid),build_tree(rc,mid+1,r);
    pushup(cur);
}
il updata(int cur,int l,int r,int pos,int k){
    if(l==r) return T[cur].mn=T[cur].mx=k,T[cur].mx_pre=pre[l],void();
    if(mid>=pos) updata(lc,l,mid,pos,k);
    else updata(rc,mid+1,r,pos,k);
    pushup(cur);
}
it query_mx(int cur,int l,int r,int L,int R){
    if(l>=L&&r<=R) return T[cur].mx;
    ri res=0;
    if(mid>=L) res=max(res,query_mx(lc,l,mid,L,R));
    if(R>mid) res=max(res,query_mx(rc,mid+1,r,L,R));
    return res;
}
it query_mn(int cur,int l,int r,int L,int R){
    if(l>=L&&r<=R) return T[cur].mn;
    ri res=INT_MAX;
    if(mid>=L) res=min(res,query_mn(lc,l,mid,L,R));
    if(R>mid) res=min(res,query_mn(rc,mid+1,r,L,R));
    return res;
}
it query_pre(int cur,int l,int r,int L,int R){
    if(l>=L&&r<=R) return T[cur].mx_pre;
    ri res=-1;
    if(mid>=L) res=max(res,query_pre(lc,l,mid,L,R));
    if(R>mid) res=max(res,query_pre(rc,mid+1,r,L,R));
    return res;
}
struct Tree{
    int d;
}T1[MAXN<<2];
int c[MAXN];
il build(int cur,int l,int r){
    if(l==r) return T1[cur].d=c[l],void();
    build(lc,l,mid),build(rc,mid+1,r);
    T1[cur].d=gcd(T1[lc].d,T1[rc].d);
}
il updata_d(int cur,int l,int r,int pos){
    if(l==r) return T1[cur].d=c[pos],void();
    if(mid>=pos) updata_d(lc,l,mid,pos);
    else updata_d(rc,mid+1,r,pos);
    T1[cur].d=gcd(T1[lc].d,T1[rc].d);
}
it query_d(int cur,int l,int r,int L,int R){
    if(l>=L&&r<=R) return T1[cur].d;
    ri res=0;
    if(mid>=L) res=gcd(res,query_d(lc,l,mid,L,R));
    if(R>mid) res=gcd(res,query_d(rc,mid+1,r,L,R));
    return res;
}
it solve(int l,int r,int k){
    if(l==r) return 1;
    ri mx=query_mx(1,1,n,l,r),mn=query_mn(1,1,n,l,r),d=query_d(1,1,n-1,l,r-1),mx_pre=query_pre(1,1,n,l,r);
    if(mx-mn!=1ll*(r-l)*k) return 0;
    if(k&&mx_pre>=l) return 0;
    if(d!=k) return 0;
    return 1;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n),read(m);
    for(ri i=1;i<=n;++i) read(val[i]);
    for(ri i=1;i<n;++i) c[i]=abs(val[i+1]-val[i]);
    for(ri i=1;i<=n;++i){
        if(!mp[val[i]].size()) pre[i]=-1;
        else{
            ite=mp[val[i]].end();--ite;
            pre[i]=*ite;
        }
        mp[val[i]].insert(i);
    }
    build_tree(1,1,n),build(1,1,n-1);
    for(ri i=1;i<=m;++i){
        read(opt),read(x),read(y);
        x^=cnt,y^=cnt;
        if(opt==1){
            ite=mp[val[x]].find(x);
            if(ite!=mp[val[x]].end()) ++ite,pre[*ite]=pre[x],updata(1,1,n,*ite,val[*ite]);
            mp[val[x]].erase(x),val[x]=y;
            ite=mp[val[x]].lower_bound(x);
            if(ite!=mp[val[x]].end()) pre[*ite]=x,updata(1,1,n,*ite,val[*ite]);
            if(ite==mp[val[x]].begin()) pre[x]=-1;
            else --ite,pre[x]=*ite,mp[val[x]].insert(x);
            c[x]=abs(val[x+1]-val[x]),c[x-1]=abs(val[x]-val[x-1]);
            updata(1,1,n,x,y),updata_d(1,1,n-1,x);
            if(x-1) updata_d(1,1,n-1,x-1);
        }
        if(opt==2){
            read(k),k^=cnt;
            if(solve(x,y,k)) puts("Yes"),++cnt;
            else puts("No");
        }
    }
    return 0;
}

总结

这道题需要考虑到能构成等差数列的多种条件，而且边界需要特别注意，但是好像能用 hash 乱搞过去。

就直接存一下区间最大，最小，区间和，元素的平方和，立方和，然后对于 d ，我们根据最大值和最小值，算出以上的 3 个值的 hash 值，然后判断相等即可。

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

闲扯

题面

Solution

Code

总结

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