题解 P11373 【CZOI-R2 天平】

· · 题解

题意简述

给出一个序列 a，可以进行增、删、区间加和询问操作。询问操作为给定 v 问是否存在一组解 x_l,x_{l+1},\cdots,x_r，使得 \sum_{i=l}^ra_ix_i=v.

前置数学知识

辗转相除法

b,&a=0\\ \gcd(b\bmod a,a),&a\neq0 \end{cases}

裴蜀定理

关于 x_1,x_2,\cdots,x_n 的方程 \sum_{i=1}^na_ix_i=b，a_i,b\in\mathbb{Z} 有整数解的充要条件是 \gcd(a_1,a_2,\cdots,a_n)\mid b.

解题思路

根据翡蜀定理，每次询问操作相当于问区间最大公约数是否能整除给定的值。

能够使用 O(\log n) 进行区间修改、增、删、查的数据结构最经典的就是平衡树。

假设进行 [l,r] 区间加操作前的序列为 a，操作后的序列为 a'，则可以发现 \gcd(a_l-a_{l+1},a_{l+1}-a_{l+2},\cdots,a_{r-1}-a_r)=\gcd(a'_l-a'_{l+1},a'_{l+1}-a'_{l+2},\cdots,a'_{r-1}-a'_r)，而根据辗转相除法的原理，\forall i\in[l,r],\gcd(a_l,a_{l+1},\cdots,a_r)=\gcd(a_i,\gcd(a_l-a_{l+1},a_{l+1}-a_{l+2},\cdots,a_{r-1}-a_r)).

所以我们可以使用平衡树，每个节点维护两个值：序列中的一个值、子树区间的差值的最大公约数。

为了单次操作都是 O(\log n)，区间加需要使用懒标记。

总时间复杂度 O(n\log n).

AC 代码

#include<bits/stdc++.h>
using namespace std;
int root,tot;
struct node{
    int siz,cc,ls,rs;
    long long val,gcd,tag;
}nd[200010];
long long a[100000];
long long gcd(long long a,long long b){return a?gcd(b%a,a):b;}
void pushdown(int x){//标记下传
    nd[x].val+=nd[x].tag;
    if(nd[x].rs)nd[nd[x].rs].tag+=nd[x].tag;
    if(nd[x].ls)nd[nd[x].ls].tag+=nd[x].tag;
    nd[x].tag=0;
}
void update_gcd(int n){//更新区间差值gcd
    if(nd[n].tag)pushdown(n);
    if(nd[n].ls&&nd[nd[n].ls].tag)pushdown(nd[n].ls);
    if(nd[n].rs&&nd[nd[n].rs].tag)pushdown(nd[n].rs);
    nd[n].gcd=gcd(nd[n].ls?gcd(nd[nd[n].ls].gcd,abs(nd[nd[n].ls].val-nd[n].val)):0
                ,nd[n].rs?gcd(nd[nd[n].rs].gcd,abs(nd[nd[n].rs].val-nd[n].val)):0);
}
void split(int n,int siz,int &L,int &R){//分裂
    if(!n){L=R=0;return;}
    if(nd[n].siz==siz){L=n;R=0;return;}
    if(!siz){L=0;R=n;return;}
    if(nd[n].tag)pushdown(n);
    if((nd[n].ls?nd[nd[n].ls].siz:0)==siz)
    {L=nd[n].ls;R=n;nd[n].ls=0;}
    else if((nd[n].ls?nd[nd[n].ls].siz:0)<siz)
    {L=n;split(nd[n].rs,siz-(nd[n].ls?nd[nd[n].ls].siz:0)-1,nd[n].rs,R);}
    else{R=n;split(nd[n].ls,siz,L,nd[n].ls);}
    nd[n].siz=1+(nd[n].ls?nd[nd[n].ls].siz:0)+(nd[n].rs?nd[nd[n].rs].siz:0);
    update_gcd(L);update_gcd(R);
}
int merge(int L,int R){//合并
    if(!(L&&R))return L|R;
    if(nd[L].tag)pushdown(L);
    if(nd[R].tag)pushdown(R);
    if(nd[L].cc<nd[R].cc){
        nd[L].rs=merge(nd[L].rs,R);
        nd[L].siz=1+(nd[L].ls?nd[nd[L].ls].siz:0)+(nd[L].rs?nd[nd[L].rs].siz:0);
        update_gcd(L);
        return L;
    }
    else{
        nd[R].ls=merge(L,nd[R].ls);
        nd[R].siz=1+(nd[R].ls?nd[nd[R].ls].siz:0)+(nd[R].rs?nd[nd[R].rs].siz:0);
        update_gcd(R);
        return R;
    }
}
int build(long long *L,int n,int cc=-1000000000){
//从数组区间建树
    if(!n)return 0;
    int r=++tot;
    nd[r].val=L[n>>1];nd[r].cc=cc+1+rand();nd[r].tag=0;
    nd[r].ls=build(L,n>>1,nd[r].cc);
    nd[r].rs=build(L+(n>>1)+1,n-1-(n>>1),nd[r].cc);
    nd[r].siz=1+(nd[r].ls?nd[nd[r].ls].siz:0)+(nd[r].rs?nd[nd[r].rs].siz:0);
    nd[r].gcd=gcd(nd[r].ls?gcd(nd[nd[r].ls].gcd,abs(nd[nd[r].ls].val-nd[r].val)):0,
                nd[r].rs?gcd(nd[nd[r].rs].gcd,abs(nd[nd[r].rs].val-nd[r].val)):0);
    return r;
}
long long check_gcd(int Lsiz,int Rsiz){
//查询区间[Lsiz,Rsiz]的gcd
    int L,M,R;
    split(root,Rsiz,M,R);split(M,Lsiz-1,L,M);
    long long ret=gcd(nd[M].gcd,nd[M].val+nd[M].tag);
    root=merge(L,merge(M,R));
    return ret;
}
void add(long long val,int Lsiz,int Rsiz){
//[Lsiz,Rsiz]区间加
    int L,M,R;
    split(root,Rsiz,M,R);split(M,Lsiz-1,L,M);
    nd[M].tag+=val;
    root=merge(L,merge(M,R));
}
void insert(int pos,long long val){
//插入
    int L,R;
    split(root,pos,L,R);
    nd[++tot].cc=rand();nd[tot].siz=1;
    nd[tot].val=val;
    nd[tot].gcd=nd[tot].tag=nd[tot].ls=nd[tot].rs=0;
    root=merge(L,merge(tot,R));
}
void del(int pos){
//删除
    int L,M,R;
    split(root,pos-1,L,M);split(M,1,M,R);
    root=merge(L,R);
}
int main(){
    int n,q;scanf("%d%d",&n,&q);
    for(int i=0;i<n;i++)scanf("%lld",a+i);
    root=build(a,n);
    while(q--){
        char c=getchar();
        while(c<'A'||c>'Q')c=getchar();
        if(c=='I'){
            int x;long long v;scanf("%d%lld",&x,&v);
            insert(x,v);n++;
        }else if(c=='D'){
            int x;scanf("%d",&x);
            del(x);n--;
        }else if(c=='A'){
            int l,r;long long v;scanf("%d%d%lld",&l,&r,&v);
            add(v,l,r);
        }else{
            int l,r;long long v;scanf("%d%d%lld",&l,&r,&v);
            puts(v%check_gcd(l,r)==0?"YES":"NO");
        }
    }
    return 0;
}