题解：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)

。有点不太懂为什么其他题解都要用懒标记？

代码：

CPP

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

题解：P11373 「CZOI-R2」天平

文章操作

相关推荐

评论

题解：P11373 「CZOI-R2」天平