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

· · 题解

不难证明，对于一个数列\:[l,r]，他重新排列组合之后可以变成一个公差为\:k\:的等差数列的充分必要条件有：

  1. 区间内最大值与最小值之差等于\:k \times (r-l) 。 a
  3. 区间内不存在重复数字。

前两个很好理解，也很好用线段树好实现，问题就是如何用线段树维护第3个条件。
对于一个下标，维护这个下标的前驱后继。
这里的前驱指在这个下标之前第一个与这个下标所对应的数相等的数所对应的下标，用\:\operatorname{anc}_i\:表示。如果没有，则\:\operatorname{anc}_i\:设为\:0。
后继则指的是在这个下标之后第一个与这个下标所对应的数相等的数所对应的下标，用\:\operatorname{suc}_i\:表示。如果没有，则\:\operatorname{suc}_i\:设为\:n+1。
如果一个数下标为\:i\:在\:[l,r]\:区间内有重复数字，满足\:\operatorname{anc}_i \ge l\:或者\:\operatorname{suc}_i \le r。
不难证明，对于一个区间\:[l,r]，维护其内部所有元素的前驱的最大值，如果这个最大值\:\lt l，那么这个区间不存在重复数字。
那么接下来的问题是：如何用\:O(\log n)\:的时间复杂度动态维护前驱后继？
对于每一个值\:val，记录这个值出现的每一个位置。
如果将下标\:x\:的数改成\:y，那么首先要修改的就是其前驱的后继与其后继的前驱。（类似链表）

\operatorname{anc}_{\operatorname{suc}_i}=\operatorname{anc}_i,\operatorname{suc}_{\operatorname{anc}_i}=\operatorname{suc}_{i}

然后用二分查找（\operatorname{lower\_bound}）找到值为\:y\:的下标中最后一个\:\lt i\:的数和第一个\:\gt i\:的数，分别就是\:i\:的新前驱后继。
然后再分别修改新前驱的新后继和新后继的新前驱即可。

综上，我们需要构建两个线段树，一个维护原数组的区间最大值、最小值和前驱最大值，另一个维护差分数组的区间\:\gcd。

代码细节较多，比较玩心态，反正我做了很久，调了半天才发现我强制在线的异或那一行写在了输入之前……哭笑不得。
然后，就是代码：

AC code:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+5;
const int inf=1e18+7;
#define lson (u<<1)
#define rson (u<<1|1)
#define mid ((l+r)>>1)
int a[maxn],d[maxn];//d是a的差分数组 
int n,m,cnt;
map<int,set<int>> mp;//储存数出现的位置 
int anc[maxn],suc[maxn];//前驱后继储存 
void remove(int x){//把一个数x从mp[a[x]]中删去，同时更新前驱后继 
    auto &s=mp[a[x]];
    auto it=s.find(x);
    if(it==s.end())return;//没找到 
    if(it!=s.begin()){//确认有后继 
        auto pre=prev(it);
        suc[*pre]=suc[x];
    }
    if(next(it)!=s.end()){//确认有前驱 
        auto nex=next(it);
        anc[*nex]=anc[x];
    }
    s.erase(it);
    if(s.empty())mp.erase(a[x]);
}
void insert(int x,int y){//把一个数x插入mp[y]，同时更新前驱后继 
    a[x]=y;//更新a数组因为差分线段树会用到 
    auto &s=mp[y];
    auto it=s.lower_bound(x);
    if(it!=s.end()){//有后继 
        suc[x]=*it;
        anc[*it]=x;
    }else{//没有后继 
        suc[x]=n+1;
    }
    if(it!=s.begin()){//有前驱 
        auto pre=prev(it);
        anc[x]=*pre;
        suc[*pre]=x;
    }else{//没有前驱 
        anc[x]=0;
    }
    s.insert(x);
}
void change(int x,int y){
    if(a[x]==y)return;//这个等于没改 
    remove(x);
    insert(x,y);
}
struct seg_tree{ 
    struct treenode{
        int l,r,mx,mn,mxanc;
        /*
        l,r:左右端点
        mx,mn:区间最大值与最小值
        mxanc:最小前驱 
        */
    }tree[maxn<<2];
    void pushup(int u){
        tree[u].mx=max(tree[lson].mx,tree[rson].mx);
        tree[u].mn=min(tree[lson].mn,tree[rson].mn);
        tree[u].mxanc=max(tree[lson].mxanc,tree[rson].mxanc);
    }
    void build(int u,int l,int r){
        tree[u].l=l,tree[u].r=r;
        if(l==r){
            tree[u].mx=tree[u].mn=a[l];
            tree[u].mxanc=anc[l];
            return;
        }
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(u);
    }
    void update(int u,int p,int x){
        int l=tree[u].l,r=tree[u].r;
        if(l>p||r<p)return;
        if(l==r){
            change(p,x);
            tree[u].mxanc=anc[p];
            tree[u].mx=tree[u].mn=x;
            return;
        }
        if(p<=mid)update(lson,p,x);
        else update(rson,p,x);
        pushup(u);
    }
    int querymn(int u,int L,int R){
        int l=tree[u].l,r=tree[u].r;
        if(l>R||r<L)return inf;
        if(L<=l&&r<=R)return tree[u].mn;
        return min(querymn(lson,L,R),querymn(rson,L,R));
    }
    int querymx(int u,int L,int R){
        int l=tree[u].l,r=tree[u].r;
        if(l>R||r<L)return -inf;
        if(L<=l&&r<=R)return tree[u].mx;
        return max(querymx(lson,L,R),querymx(rson,L,R));
    }
    int queryanc(int u,int L,int R){
        int l=tree[u].l,r=tree[u].r;
        if(l>R||r<L)return -1;
        if(L<=l&&r<=R)return tree[u].mxanc;
        return max(queryanc(lson,L,R),queryanc(rson,L,R));
    }//板子，不必多说 
}tree_a;            //维护原数组的区间最值与最大前驱 
struct segtree{
    struct treenode{
        int l,r;
        int gcd;
    }tree[maxn<<2];
    void pushup(int u){
        tree[u].gcd=__gcd(tree[lson].gcd,tree[rson].gcd);
    }
    void build(int u,int l,int r){
        tree[u].l=l,tree[u].r=r;
        if(l==r){
            tree[u].gcd=d[l];
            return;
        }
        build(lson,l,mid);
        build(rson,mid+1,r);
        pushup(u);
    }
    void update(int u,int p,int x){
        int l=tree[u].l,r=tree[u].r;
        if(l>p||r<p)return;
        if(l==r){
            tree[u].gcd+=x;
            return;
        }
        update(lson,p,x);
        update(rson,p,x);
        pushup(u);
    }
    int querygcd(int u,int L,int R){
        int l=tree[u].l,r=tree[u].r;
        if(l>R||r<L)return 0;
        if(L<=l&&r<=R)return abs(tree[u].gcd);
        return __gcd(querygcd(lson,L,R),querygcd(rson,L,R));
    }
}tree_d;                //维护差分数组的gcd 
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];
        insert(i,a[i]);
    }
    tree_a.build(1,1,n);
    tree_d.build(1,1,n);
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x,y;
            cin>>x>>y;
            x^=cnt,y^=cnt;//强制在线 
            int val=a[x],oldsuc=suc[x];
            tree_a.update(1,x,y);
            int newsuc=suc[x];
            tree_a.update(1,oldsuc,a[oldsuc]);//更新后继在线段树中最大前驱的信息 
            tree_a.update(1,newsuc,a[newsuc]);//更新新后继在线段树中新最大前驱的信息
            //此处因为原后继和新后继的前驱都发生了改变，但是线段树内部的最大前驱却没有改完全
            //所以需要把它们放进线段树中重新递归把信息上传一次 
            tree_d.update(1,x,y-val);//更改差分数组信息 
            if(x!=n)tree_d.update(1,x+1,val-y);//注意要改两个点 
        }else{
            int l,r,k;
            cin>>l>>r>>k;
            l^=cnt,r^=cnt,k^=cnt;
            if(l==r){//特判：l,r相等时仅有一个数，是等差数列 
                cout<<"Yes"<<endl;
                cnt++;
                continue;
            }
            int mn=tree_a.querymn(1,l,r);//区间最小值 
            int mx=tree_a.querymx(1,l,r);//区间最大值 
            int mxanc=tree_a.queryanc(1,l,r);//区间最大前驱 
            int gcd=tree_d.querygcd(1,l+1,r);//区间差值gcd 
            if(k==0){
                if(mx==mn&&mxanc>=l){//特判：当公差为0时，所有元素相同才是等差数列 
                    cout<<"Yes"<<endl;
                    cnt++;
                }
                else cout<<"No"<<endl;
                continue;
            }
            if((mx-mn==(r-l)*k)&&mxanc<l&&gcd==k){//3个条件：最大最小差值为(r-l)*k，最大前驱小于l区间元素互不相同，差值gcd等于公差 
                cout<<"Yes"<<endl;
                cnt++;
            }else{
                cout<<"No"<<endl;
            }
        }
    }
    return 0;
}