「CZOI-R2」天平 题解

· · 题解

「CZOI-R2」天平 题解

题目分析

首先解决如何判断一个质量是否能被表出的问题。

形式化的，需要判断是否存在一个序列 c，满足 \forall c_i\in \Z，使得 a_lc_l+a_{l+1}c_{l+1}+\cdots+a_rc_r=v。

这是裴蜀定理可以推广到 n 个整数的情形，存在序列 c 当且仅当 \gcd\{a_l,a_{l+1},\cdots,a_r\}\mid v。

所以只需判断 v 是否是 \gcd\{a_l,a_{l+1},\cdots,a_r\} 的倍数即可。

实现方法

SubTask #1

留给没有看出转化成 \gcd 问题的人，暴力 dfs 也许能拿到？

SubTask #2

因为 1\le n,q\le 4\times 10^2，所以可以暴力维护所有操作，时间复杂度 O(qn\log m)。

#include<bits/stdc++.h>
#define int long long
#define GCD __gcd
using namespace std;
int n,q;vector<int>f;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    f.push_back(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        f.push_back(a);
    }
    while(q--){
        char op;cin>>op;
        if(op=='I'){
            int x,v;cin>>x>>v;
            f.insert(f.begin()+x+1,v);
        }
        if(op=='D'){
            int x;cin>>x;
            f.erase(f.begin()+x);
        }
        if(op=='A'){
            int l,r,v;cin>>l>>r>>v;
            for(int i=l;i<=r;i++)f[i]+=v;
        }
        if(op=='Q'){
            int l,r,v;cin>>l>>r>>v;
            int g=0;
            for(int i=l;i<=r;i++)g=GCD(g,f[i]);
            cout<<(v%g?"NO":"YES")<<endl; 
        }
    }
    return 0;
}

SubTask #3

没有插入和删除，可以使用线段树静态查询，思考如何实现区间 \gcd。

这里我们可以配合差分过后的序列 b 维护区间 \gcd，思考一下为什么：

\gcd\{a\}=\gcd\{\gcd\{a_1,a_2\},\gcd\{a_2,a_3\},\cdots,\gcd\{a_{n-1},a_n\}\}

又因更相减损术（古人的智慧）：\gcd(x,y)=\gcd(x,y-x)，可以得到

\gcd\{a\}=\gcd\{\gcd\{a_1,a_2-a_1\},\gcd\{a_2,a_3-a_2\},\cdots,\gcd\{a_{n-1},a_n-a_{n-1}\}\}

发现 a_2,a_3,\cdot\cdot\cdot,a_{n-1} 已经被左边两项囊括，所以原式等于 \gcd\{a_1,b_2,b_3,\cdots,b_n\}。

这可以推广到左端点和右端点任意的情况，于是我们在上的每一个节点分别存原值、差分后的值、差分后的值的 \gcd，最后每次询问回答 \gcd(a_l,\gcd\{b_{l+1},b_{l+2},\cdots,b_r) 的值就行了。

时间复杂度：O((n+q\log n)\log m)。

#include<bits/stdc++.h>
#define int long long
#define GCD __gcd
using namespace std;
const int maxn=1e6+10;
struct tree{int sum,gcd;}t[maxn<<2];
int n,q,a[maxn];
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
void pushup(int p){t[p]={t[ls(p)].sum+t[rs(p)].sum,GCD(t[ls(p)].gcd,t[rs(p)].gcd)};}
void build(int l,int r,int p){
    if(l==r)return t[p]={a[l]-a[l-1],a[l]-a[l-1]},void();
    int mid=(l+r)>>1;
    build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
}
void update(int l,int r,int k,int v,int p){
    if(l==r){
        t[p].sum+=v,t[p].gcd+=v;
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid)update(l,mid,k,v,ls(p));
    else update(mid+1,r,k,v,rs(p));
    pushup(p);
}
int qsum(int l,int r,int le,int ri,int p){
    if(l>=le&&r<=ri)return t[p].sum;
    int mid=(l+r)>>1;int ans=0;
    if(le<=mid)ans+=qsum(l,mid,le,ri,ls(p));
    if(ri>mid)ans+=qsum(mid+1,r,le,ri,rs(p));
    return ans;
}
int qgcd(int l,int r,int le,int ri,int p){
    if(l>=le&&r<=ri)return t[p].gcd;
    int mid=(l+r)>>1;int ans=0;
    if(le<=mid)ans=GCD(ans,qgcd(l,mid,le,ri,ls(p)));
    if(ri>mid)ans=GCD(ans,qgcd(mid+1,r,le,ri,rs(p)));
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,n,1);
    while(q--){
        char op;int l,r,v;
        cin>>op>>l>>r>>v;
        if(op=='A'){
            update(1,n,l,v,1);
            if(r!=n)update(1,n,r+1,-v,1);
        }
        if(op=='Q'){
            int g=abs(GCD(qgcd(1,n,l+1,r,1),qsum(1,n,1,l,1)));
            cout<<(v%g?"NO\n":"YES\n");
        }
    }
    return 0;
}

SubTask #4

换成平衡树维护序列，这里采用无旋 treap，这里讲一些实现细节。

首先，这道题目空间并不紧张，你可以不用平衡树节点回收（虽然 std 用了）。

其次，分裂和合并的时候不要无脑复制粘贴（std因为这个锅了一次），对于特殊情况要注意分类讨论。

时间复杂度：O((n+q)\log n\log m)。

#include<bits/stdc++.h>
#define int long long
#define GCD __gcd
using namespace std;
const int maxn=2e5+10;
struct Treap{
    int rt,cnt,num[maxn],val[maxn],gcd[maxn],ls[maxn],rs[maxn],siz[maxn],plz[maxn],rnd[maxn];
    queue<int>del;mt19937 maker;
    Treap(){maker.seed(time(0));}
    int newnode(int x){
        int idx;
        if(del.empty()){idx=++cnt;}else{idx=del.front(),del.pop();}
        num[idx]=x;siz[idx]=1;ls[idx]=rs[idx]=plz[idx]=0;rnd[idx]=maker();
        return idx; 
    }
    void pushdown(int x){
        if(ls[x])num[ls[x]]+=plz[x],plz[ls[x]]+=plz[x];
        if(rs[x])num[rs[x]]+=plz[x],plz[rs[x]]+=plz[x];
        plz[x]=0;
    }
    void pushup(int x){
        siz[x]=siz[ls[x]]+siz[rs[x]]+1;
        gcd[x]=GCD(GCD(gcd[ls[x]],gcd[rs[x]]),val[x]);
    }
    void split(int x,int k,int &rt1,int &rt2){
        if(!x){rt1=rt2=0;return;}
        pushdown(x);
        if (siz[ls[x]]<k)rt1=x,split(rs[x],k-siz[ls[x]]-1,rs[x],rt2);
        else rt2=x,split(ls[x],k,rt1,ls[x]);
        pushup(x);
    }
    int merge(int x,int y){
        if(!x||!y)return x+y;
        pushdown(x),pushdown(y);
        if(rnd[x]<rnd[y]){ls[y]=merge(x,ls[y]),pushup(y);return y;}
        else{rs[x]=merge(rs[x],y),pushup(x);return x;}
    }
    int getidx(int x){
        int rt1,rt2,rt3,ans;
        split(rt,x-1,rt1,rt2),split(rt2,1,rt2,rt3),ans=rt2;
        rt=merge(merge(rt1,rt2),rt3);
        return ans;
    }
    int getgcd(int l,int r){
        int rt1,rt2,rt3,ans;
        split(rt,l-1,rt1,rt2),split(rt2,r-l+1,rt2,rt3),ans=gcd[rt2];
        rt=merge(merge(rt1,rt2),rt3);
        return ans;
    }
    void insert(int x,int y){
        int rt1,rt2,rt3,node=newnode(y);
        val[node]=gcd[node]=y-num[getidx(x)];
        split(rt,x,rt1,rt3),split(rt3,1,rt2,rt3);
        if(rt2)val[rt2]=gcd[rt2]=num[rt2]-y;
        rt=merge(merge(rt1,node),merge(rt2,rt3));
    }
    void remove(int x){
        int rt1,rt2,rt3,tmp=num[getidx(x-1)];
        split(rt,x,rt1,rt2),split(rt2,1,rt2,rt3),val[rt2]=gcd[rt2]=num[rt2]-tmp;
        rt=merge(merge(rt1,rt2),rt3);
        split(rt,x-1,rt1,rt2),split(rt2,1,rt2,rt3),del.push(rt2);
        rt=merge(rt1,rt3);
    }
    void update(int l,int r,int x){
        int rt1,rt2,rt3;
        split(rt,l-1,rt1,rt2),split(rt2,r-l+1,rt2,rt3);
        num[rt2]+=x,plz[rt2]+=x,rt=merge(merge(rt1,rt2),rt3);
        split(rt,l-1,rt1,rt2),split(rt2,1,rt2,rt3);
        val[rt2]+=x,gcd[rt2]+=x,rt=merge(merge(rt1,rt2),rt3);
        split(rt,r,rt1,rt2),split(rt2,1,rt2,rt3);
        if(rt2)val[rt2]-=x,gcd[rt2]-=x;
        rt=merge(merge(rt1,rt2),rt3);
    }
    int query(int l,int r){return GCD(num[getidx(l)],getgcd(l+1,r));}
}t;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++){
        int a;cin>>a;t.insert(i-1,a);
    }
    while(q--){
        char op;cin>>op;
        if(op=='I'){
            int x,v;cin>>x>>v;
            t.insert(x,v);
        }if(op=='D'){
            int x;cin>>x;
            t.remove(x);
        }if(op=='A'){
            int l,r,v;cin>>l>>r>>v;
            t.update(l,r,v);
        }if(op=='Q'){
            int l,r,v;cin>>l>>r>>v;
            cout<<(v%t.query(l,r)?"NO\n":"YES\n");
        }
    }
    return 0;
}