题解：P11373 「CZOI-R2」天平

· · 题解

根据裴蜀定理，有解的充要条件是 \gcd\{ a_l,a_{l+1},\cdots,a_r\} \mid v，那么就把原问题转化成了求解区间 \gcd。

如果没有插入和删除操作，考虑下怎么做。根据更相减损术 \gcd(x,y) = \gcd(x,y-x)，不难证明 \gcd \{ a_l,a_{l+1},\cdots,a_{r}\} = \gcd \{a_l,a_{l+1}-a_l,a_{r}-a_{r-1}\}，那么通过线段树维护差分数组，就可以把区间加法转化成单点加法，这样维护区间 \gcd 就比较容易了，具体可以参考 P10463。

现在有了插入和删除操作，只要把线段树换成平衡树就行了，用 FHQ-Treap 就非常方便了，复杂度 \mathcal O((n+q) \log n \log V)。有点不太懂为什么其他题解都要用懒标记？

代码：


#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,q,a[N],tot,rt;
char opt;
struct node{
    int val,key,ls,rs,sum,d,sz;
}tr[N];
void push_up(int x){
    tr[x].sz=tr[tr[x].ls].sz+tr[tr[x].rs].sz+1;
    tr[x].sum=tr[tr[x].ls].sum+tr[tr[x].rs].sum+tr[x].val;
    tr[x].d=abs(__gcd(__gcd(tr[tr[x].ls].d,tr[tr[x].rs].d),tr[x].val));
}
void split(int x,int k,int &L,int &R){
    if(!x){
        L=R=0;
        return;
    }
    if(tr[tr[x].ls].sz<k){
        L=x;
        split(tr[x].rs,k-tr[tr[x].ls].sz-1,tr[x].rs,R);
    }
    else{
        R=x;
        split(tr[x].ls,k,L,tr[x].ls);
    }
    push_up(x);
}
int merge(int x,int y){
    if(!x||!y) return x+y;
    if(tr[x].key<tr[y].key){
        tr[x].rs=merge(tr[x].rs,y);
        push_up(x);
        return x;
    }
    tr[y].ls=merge(x,tr[y].ls);
    push_up(y);
    return y;
}
int New(int v){
    tr[++tot]={v,rand(),0,0,v,v,1};
    return tot;
}
int query(int h){
    int x,y;
    split(rt,h,x,y);
    int ans=tr[x].sum;
    rt=merge(x,y);
    return ans;
}
void add(int h,int v){
    int x,y,z;
    split(rt,h,x,z);
    split(x,h-1,x,y);
    tr[y].val+=v;
    push_up(y);
    rt=merge(merge(x,y),z);
}
int qry(int l,int r){
    int x,y,z,v=query(l);
    split(rt,r,x,z);
    split(x,l,x,y);
    int ans=__gcd(v,tr[y].d);
    rt=merge(merge(x,y),z);
    return ans;
}
void insert(int h,int v){
    int x,y,w=query(h);
    if(h<n){
        add(h+1,w);
        add(h+1,-v);
    }
    split(rt,h,x,y);
    rt=merge(merge(x,New(v-w)),y);
}
void dlt(int h){
    int x,y,z;
    if(h<n){
        add(h+1,query(h));
        add(h+1,-query(h-1));
    }
    split(rt,h,x,z);
    split(x,h-1,x,y);
    rt=merge(x,z);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i],rt=merge(rt,New(a[i]-a[i-1]));
    for(int x,y,v;q;q--){
        cin>>opt>>x;
        if(opt=='I'){
            cin>>v;n++;
            insert(x,v);
        }
        else if(opt=='D') dlt(x),n--;
        else if(opt=='A'){
            cin>>y>>v;
            add(x,v);
            if(y<n) add(y+1,-v);
        }
        else if(opt=='Q'){
            cin>>y>>v;
            int d=qry(x,y);
            if(!(v%d)) cout<<"YES\n";
            else cout<<"NO\n";
        }
        tr[0]={0,0,0,0,0,0,0};
    }
    return 0;
}