BZOJ 5028 小z的加油站

Time limit 10000 ms
Memory limit 262144 kB
OS Linux

感想

树上动态gcd的第二题也好了。

[x] BZOJ 2257 [JSOI2009]瓶子和燃料
[x] BZOJ 5028 小z的加油站
[ ] CodeChef DGCD Dynamic GCD

解题思路

由上一题 [JSOI2009]瓶子和燃料可知，这题这样子折腾就是在求区间最大公因数，这里还带上了区间加，所以需要另外一些性质——

众所周知，区间加作用到原序列上，相当于差分序列的两次单点修改（操作范围的右边顶着边界，那就是1次单点修改）。由更相减损可知，原序列总的gcd等于差分序列总的gcd，即差分一下gcd不变（此时求gcd的函数要注意将小于零的参数换成其绝对值进行计算，因为更相减损是大的减小的）。

\[\gcd\left(a_{1}, a_{2}, a_{3}, \dots, a_{n-2}, a_{n-1}, a_{n}\right)
\]

\[=\gcd \left(a_{1}, a_{2}-a_{1}, a_{3}-a_{2}, \ldots a_{n-1}-a_{n-2}, a_{n}-a_{n-1}\right)
\]

设$a_0=0$，$d_i=a_i-a_{i-1}$（差分数组），于是把上式推广到其他区间——

\[\gcd\left(a_{l}, a_{l+1}, a_{l+2}, \dots, a_{r-2}, a_{r-1}, a_{r}\right)
\]

\[=\gcd\left( a_{l} , \gcd (d_{l+1}, d_{l+2}, \ldots, d_{r})\right)
\]

\[=\gcd\left(\sum_{i=1}^{l} d_{l} , \gcd \left(d_{l+1}, d_{l+2}, \ldots, d_{r}\right)\right)
\]

又因为gcd满足区间加法，于是，我们就可以用线段树维护差分序列的区间和、gcd。

顺便，Hint里出现的那个$L>R$意思应该不是说数据有锅，而是说，当查询的区间长度为1时，要注意特判。

观察上式——$$\gcd\left(\sum_{i=1}^{l} d_{l} , \gcd \left(d_{l+1}, d_{l+2}, \ldots, d_{r}\right)\right)$$

对于这一项$$\gcd \left(d_{l+1}, d_{l+2}, \ldots, d_{r}\right)$$

当$l=r$，即查询区间长度为1时，会出现$l+1>r$的情况，此时这一项应该直接返回0，以防止干扰结果。或者在其他地方特判一下也行。

源代码

#include<stdio.h>

const int MAXN=1e5+5;

long long gcd(long long x,long long y)

{

	if(x<0) x=-x;

	if(y<0) y=-y;

	return y==0?x:gcd(y,x%y);

}//更相减损是大的减小的

int n,m;

long long d[MAXN];//差分数组

struct Segtree{

	long long g,sum;

}t[MAXN<<2];//维护差分数组的线段树

void pushup(int x)

{

	t[x].g=gcd(t[x<<1].g,t[x<<1|1].g);

	t[x].sum=t[x<<1].sum+t[x<<1|1].sum;

}

void build(int x,int l,int r)

{

	if(l==r)

	{

		t[x].g=t[x].sum=d[l];

		return;

	}

	int mid=l+r>>1;

	build(x<<1,l,mid);

	build(x<<1|1,mid+1,r);

	pushup(x);

}

void update(int x,int l,int r,int pos,int k)//pos处增加k

{

	if(l==r)

	{

		t[x].sum+=k;

		t[x].g+=k;

		return;

	}

	int mid=l+r>>1;

	if(pos<=mid) update(x<<1,l,mid,pos,k);

	else update(x<<1|1,mid+1,r,pos,k);

	pushup(x);

}

long long quesum(int x,int l,int r,int ql,int qr)

{

	if(ql<=l&&r<=qr)

		return t[x].sum;

	long long ans=0;

	int mid=l+r>>1;

	if(ql<=mid) ans+=quesum(x<<1,l,mid,ql,qr);

	if(qr>mid) ans+=quesum(x<<1|1,mid+1,r,ql,qr);

	return ans;

}

long long quegcd(int x,int l,int r,int ql,int qr)

{

	if(ql>qr) return 0;//特判这个

	if(ql<=l&&r<=qr)

		return t[x].g;

	long long ans;

	int mid=l+r>>1;

	if(qr<=mid) ans=quegcd(x<<1,l,mid,ql,qr);

	else if(ql>mid) ans=quegcd(x<<1|1,mid+1,r,ql,qr);

	else ans=gcd(quegcd(x<<1,l,mid,ql,qr),quegcd(x<<1|1,mid+1,r,ql,qr));

	return ans;

}

inline long long opt1(int l,int r)//区间询问gcd

{

	return gcd(quesum(1,1,n,1,l),quegcd(1,1,n,l+1,r));

}

void opt2(int l,int r,int k)//区间增加k

{

	update(1,1,n,l,k);

	if(r<n) update(1,1,n,r+1,-k);

}

int main()

{

	//freopen("test.in","r",stdin);

	scanf("%d%d",&n,&m);

	d[0]=0;

	for(int i=1;i<=n;i++)

		scanf("%lld",d+i);

	for(int i=n;i>1;i--)

		d[i]-=d[i-1];

	build(1,1,n);

	while(m--)

	{

		int opt,l,r,k;

		scanf("%d%d%d",&opt,&l,&r);

		if(opt==1)

		{

			printf("%lld\n",opt1(l,r));

		}

		else

		{

			scanf("%d",&k);

			opt2(l,r,k);

		}

	}

	return 0;

}

巴特西

BZOJ 5028 小z的加油站

感想

解题思路

源代码

最新文章

热门文章