题解 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 代码 ```cpp #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; } ```

题解 P11373 【CZOI-R2 天平】

文章操作

题意简述

前置数学知识

辗转相除法

相关推荐

评论

题解 P11373 【CZOI-R2 天平】