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

da32s1da · 2019-04-02 08:16:01 · 题解

维护x次方求和好像都能卡。。

考虑什么时候能组成等差数列。

首先\mathrm{max-min=(r-l)k}
其次相邻两数差的绝对值的\gcd是k
区间[l,r]内的数不重复

满足性质1。我们把[l,r]内的数从小到大排序，减去最小值，得到\{0,a,b,c,\cdots,(r-l)k\}

满足性质2。说明a,b,c,\cdots都是k的倍数。都除以k，得到\{0,a',b',c',\cdots,r-l\}

满足性质3。数不重复，那么a',b',c',\cdots只能是1,2,3,\cdots

所以能组成公差是k的等差数列。

现在来看需要维护什么。

最大值，最小值，前驱的最大值，区间左端点数值，区间右端点数值，差的\mathrm{gcd}

这里前驱指前面出现这个数的最后一个位置。

线段树,map,set维护即可，注意强制在线

#include<cstdio>
#include<set>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=6e5+50;
inline void rad(int &_){
    static char ch;
    while(ch=getchar(),ch<'0'||ch>'9');_=ch-48;
    while(ch=getchar(),ch<='9'&&ch>='0')_=_*10+ch-48;
}
int gcd(int u,int v){return v?gcd(v,u%v):u;}
int n,m,x,y,z,cnt,opt,las;
int a[N],pre[N],net[N];
map<int,int>mp;
set<int>s[N];
typedef set<int>::iterator IT;
struct node{
    int lval,rval,mx,mn,mnp,gc;
    node(){}
    node(int A,int B,int C,int D,int E,int F):lval(A),rval(B),mx(C),mn(D),mnp(E),gc(F){}
}r;
struct tree{
    node tre[N<<3];
    node update(node u,node v){
        return node(u.lval,v.rval,max(u.mx,v.mx),min(u.mn,v.mn),max(u.mnp,v.mnp),gcd(gcd(u.gc,v.gc),abs(u.rval-v.lval)));
    }
    void mktree(int now,int ls,int rs){
        if(ls==rs){
            tre[now]=(node){a[ls],a[ls],a[ls],a[ls],pre[ls],0};
            return;
        }
        int noww=now<<1,nrs=ls+rs>>1;
        mktree(noww,ls,nrs);
        mktree(noww|1,nrs+1,rs);
        tre[now]=update(tre[noww],tre[noww|1]);
    }
    void change(int now,int ls,int rs,int mb,node val){
        if(ls>mb||rs<mb)return;
        if(ls==rs){tre[now]=val;return;}
        int noww=now<<1,nrs=ls+rs>>1;
        change(noww,ls,nrs,mb,val);
        change(noww|1,nrs+1,rs,mb,val);
        tre[now]=update(tre[noww],tre[noww|1]);
    }
    node query(int now,int ls,int rs,int zuo,int you){
        if(ls>=zuo&&rs<=you)return tre[now];
        int noww=now<<1,nrs=ls+rs>>1;
        if(you<=nrs)return query(noww,ls,nrs,zuo,you);
        if(zuo>nrs)return query(noww|1,nrs+1,rs,zuo,you);
        return update(query(noww,ls,nrs,zuo,you),query(noww|1,nrs+1,rs,zuo,you));
    }
}t;
int main(){
    rad(n);rad(m);
    for(int i=1;i<=n;i++){
        rad(x);a[i]=x;
        if(mp.find(x)==mp.end())mp[x]=++cnt,s[cnt].insert(i);
        else{
            y=mp[x];
            z=*--s[y].end();
            pre[i]=z;
            net[z]=i;//记录每个数的前驱后继
            s[y].insert(i);//丢到set里
        }
    }
    t.mktree(1,1,n);
    for(int i=1;i<=m;i++){
        rad(opt);
        if(opt==1){
            rad(x);rad(y);
            x^=las;y^=las;
            net[pre[x]]=net[x];
            pre[net[x]]=pre[x];//修改前驱后继
            z=a[net[x]];
            t.change(1,1,n,net[x],node(z,z,z,z,pre[x],0));//修改后继在线段树内的信息
            s[mp[a[x]]].erase(x);//set中删除
            if(mp.find(y)==mp.end()){
                mp[y]=++cnt,s[cnt].insert(i);
                pre[x]=net[x]=0;
            }else{
                z=mp[y];
                IT it=s[z].lower_bound(x);//set的lower_bound找前驱后继
                if(it==s[z].begin()){//有后继无前驱
                    pre[x]=0;net[x]=*it;
                    pre[*it]=x;
                    t.change(1,1,n,*it,node(a[*it],a[*it],a[*it],a[*it],x,0));//修改后继在线段树内的信息
                }else if(it==s[z].end()){//有前驱无后继
                    --it;
                    pre[x]=*it;net[x]=0;
                    net[*it]=x;
                }else{//有前驱有后继
                    IT It=--it;++it;
                    pre[x]=*It;net[x]=*it;
                    net[*It]=x;pre[*it]=x;
                    t.change(1,1,n,*it,node(a[*it],a[*it],a[*it],a[*it],x,0));//修改后继在线段树内的信息
                }
            }
            a[x]=y;
            t.change(1,1,n,x,node(y,y,y,y,pre[x],0));//修改自身信息
        }else{
            rad(x);rad(y);rad(z);
            x^=las;y^=las;z^=las;
            r=t.query(1,1,n,x,y);
            if((r.mx-r.mn==z*(y-x))&&(r.gc==z||!r.gc)&&(r.mnp<x||!z))las++,puts("Yes");//这里注意一下
            else puts("No");
        }
    }
}