[luogu] P1890 gcd区间 线段树

前言

传送门 :
使用线段树维护区间查询操作

前言

顾名思义,我们线段树维护的就是一段区间的最大公约数,

因此建树操作 和 最基础的那个线段树 大同小异

而区间查询操作,无非就是在统计答案的时候,对左右区间各取一个 gcd即可

因此 这题很简单

CODE

const int N  = 1e3+10;
int w[N];
struct node
{
	int l,r,val;
}tr[N<<2];

inline void pushup(int u)
{
	tr[u].val = __gcd(tr[u<<1].val,tr[u<<1|1].val);
}

void build(int u,int l,int r)
{
	if(l == r)
	{
		tr[u] = {l,r,w[l]};
	}else
	{
		tr[u] ={l,r};
		int mid = (l+r) >>1;

		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}

int query(int u,int l,int r)
{
	if(tr[u].l > r || tr[u].r <l )
	return 0;
	if(tr[u].l >= l && tr[u].r <= r)
	return tr[u].val;

	return __gcd(query(u<<1,l,r),query(u<<1|1,l,r));
}
void solve()
{
	
	int n,m;
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	cin>>w[i];
	build(1,1,n);
	
	for(int i=1;i<=m;i++)
	{
		int l,r;
		cin>>l>>r;
		cout<<query(1,l,r)<<endl;
		
	}
}
int main()
{
	
	 ios::sync_with_stdio(false);
     cin.tie(0);
    // int t;cin>>t;while(t -- )
    solve();
    return 0;
}

最后

以上就是调皮山水为你收集整理的[luogu] P1890 gcd区间 线段树的全部内容，希望文章能够帮你解决[luogu] P1890 gcd区间 线段树所遇到的程序开发问题。

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