自动搬运

查看原文

来自洛谷，原作者为

	A6n6d6y6 QAQ 小A就是我

搬运于2025-08-24 23:06:48，当前版本为作者最后更新于2024-09-08 18:31:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

「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;
}