GCD of all numbers of given range of the array with point update

 Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে। 

1 L R         অ্যারের L to R index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে। 

2 pos x       অ্যারের pos তম পজিশনের ভ্যালু x বাড়িয়ে দাও। 

Solution:

সেগমেন্ট ট্রি এর রেঞ্জ কুয়েরী এবং পয়েন্ট আপডেট সম্পর্কে ধারনা থাকলেই এই প্রব্লেম সলভ করা সম্ভব। তাই বিস্তারিত আলোচনা না করে সরাসরি কোডে যাচ্ছিঃ 

	#include<bits/stdc++.h>
	#define ll long long int
	#define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++)
	#define gcd(a,b) __gcd(a,b)
	using namespace std;
	#define sz 100005
	ll ara[sz],tree[4*sz];
	void Build(ll node,ll b,ll e)
	{
	if(b == e){
	tree[node] = ara[b];
	return;
	}
	ll mid = (b+e)>>1;
	Build(node<<1 , b , mid);
	Build(1+(node<<1) , mid+1 , e);
	tree[node] = gcd(tree[node<<1] , tree[1+(node<<1)]);
	}
	ll Query(ll node,ll b,ll e,ll i,ll j)
	{
	if(e<i || b>j)
	return 0LL;
	if(b>=i && e<=j)
	return tree[node];
	ll mid = (b+e)>>1;
	ll p1 = Query(node<<1 , b , mid , i , j);
	ll p2 = Query(1+(node<<1) , mid+1 , e , i , j);
	return gcd(p1 , p2);
	}
	void Update(ll node,ll b,ll e,ll pos,ll val)
	{
	if(e<pos || b>pos)
	return;
	if(b==pos && e==pos){
	tree[node] = val;
	return;
	}
	ll mid = (b+e)>>1;
	Update(node<<1 , b , mid , pos , val);
	Update(1+(node<<1) , mid+1 , e , pos , val);
	tree[node] = gcd(tree[node<<1] , tree[1+(node<<1)]);
	}
	int main()
	{
	ll i,j,k,n,q,pos,l,r,cmd,val;
	cin>>n>>q;
	for(i=1 ; i<=n ; i++)
	cin>>ara[i];
	Build(1 , 1 , n);
	for(i=1 ; i<=q ; i++){
	cin>>cmd;
	if(cmd == 1){
	cin>>l>>r;
	ll ans = Query(1 , 1 , n , l , r);
	cout<<ans<<endl;
	}
	else{
	cin>>pos>>val;
	Update(1 , 1 , n , pos , val);
	}
	}
	return 0;
	}

view raw Range GCD with point update.cpp hosted with ❤ by GitHub

Suggested problem

Happy Coding