Master of GCD（差分数组||线段树）

题意：长度为n的数组，一开始都是1.对于区间操作l,r,x，在l~r上乘以x。x2||x3。问操作完毕之后，n个数的最大公因子是多少。
对于每个x，都等于2或者是3。那么看最大的公因子，就看各个位置上最少的2，最少的3的个数。然后乘起来就好了。线段树区间更新，区间查询。差分数组也可以做。
线段树做法：

#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;

const int maxx=1e5+100;
struct node{
	int l;
	int r;
	ll sum2;
	ll sum3;//两个值分别记录各个位置2的个数，3的个数
	ll lazy2;
	ll lazy3;
}p[maxx<<2];
int n,m;

inline ll qsm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=(ans*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return ans;
}
inline void pushup(int cur)
{
	p[cur].sum2=min(p[cur<<1].sum2,p[cur<<1|1].sum2);
	p[cur].sum3=min(p[cur<<1].sum3,p[cur<<1|1].sum3);
}
inline void pushdown(int cur)
{
	if(p[cur].lazy2)
	{
		p[cur<<1].sum2=(p[cur].lazy2+p[cur<<1].sum2)%mod;
		p[cur<<1].lazy2=(p[cur<<1].lazy2+p[cur].lazy2)%mod;
		p[cur<<1|1].sum2=(p[cur<<1|1].sum2+p[cur].lazy2)%mod;
		p[cur<<1|1].lazy2=(p[cur<<1|1].lazy2+p[cur].lazy2)%mod;
		p[cur].lazy2=0;
	}
	if(p[cur].lazy3)
	{
		p[cur<<1].sum3=(p[cur].lazy3+p[cur<<1].sum3)%mod;
		p[cur<<1].lazy3=(p[cur<<1].lazy3+p[cur].lazy3)%mod;
		p[cur<<1|1].sum3=(p[cur<<1|1].sum3+p[cur].lazy3)%mod;
		p[cur<<1|1].lazy3=(p[cur<<1|1].lazy3+p[cur].lazy3)%mod;
		p[cur].lazy3=0;
	}
}
inline void build(int l,int r,int cur)
{
	p[cur].l=l;
	p[cur].r=r;
	p[cur].lazy2=0;
	p[cur].lazy3=0;
	p[cur].sum2=0;
	p[cur].sum3=0;
	if(l==r) return ;
	int mid=l+r>>1;
	build(l,mid,cur<<1);
	build(mid+1,r,cur<<1|1);
}
inline void update(int l,int r,int v,int cur)
{
	int L=p[cur].l;
	int R=p[cur].r;
	if(l<=L&&R<=r)
	{
		if(v==2) p[cur].sum2++,p[cur].lazy2++;
		if(v==3) p[cur].sum3++,p[cur].lazy3++;
		p[cur].sum2%=mod,p[cur].lazy2%=mod;
		p[cur].sum3%=mod,p[cur].lazy3%=mod;
		return ;
	}
	pushdown(cur);
	int mid=L+R>>1;
	if(r<=mid) update(l,r,v,cur<<1);
	else if(l>mid) update(l,r,v,cur<<1|1);
	else update(l,mid,v,cur<<1),update(mid+1,r,v,cur<<1|1);
	pushup(cur);
}
int main()
{
	int l,r,x;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		build(1,n,1);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&l,&r,&x);
			update(l,r,x,1);
		}
		ll ans1=qsm(2ll,(ll)p[1].sum2)%mod;
		ll ans2=qsm(3ll,(ll)p[1].sum3)%mod;
		printf("%lldn",(ans2*ans1)%mod);
	}
	return 0;
}

努力加油a啊，(^o)/~

最后

以上就是忧心蜻蜓为你收集整理的Master of GCD（差分数组||线段树）的全部内容，希望文章能够帮你解决Master of GCD（差分数组||线段树）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。