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

এই পর্ব পড়ার আগে Range GCD & Point Update পর্বটি পড়া আবশ্যক। 

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

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

2 L R x           অ্যারের L থেকে R ইনডেক্স পর্যন্ত সংখ্যাগুলোর ভ্যালু x বাড়াতে হবে। 

Solution:

আমরা জানি, 

GCD(a , b) = GCD(a , b-a) = GCD(a-b , b) = GCD(abs(a-b) , a) = GCD(abs(a-b) , b)

GCD(a , b , c) = GCD(a , GCD(b , c))

উপরোক্ত দুটি সমীকরণ থেকে লিখতে পারি,

GCD(a , b , c) = GCD(a , GCD(b-a , c-b))

অর্থাৎ, GCD(a[l] , a[l+1] , a[l+2] , ... , a[r]) = GCD(a[l] , a[l+1]-a[l] , a[l+2]-a[l+1] , ... , a[r]-a[r-1])

এখন, এই প্রব্লেম এ আমরা দুটি সেগমেন্ট ট্রি ব্যাবহার করবো। 

১) ১ম সেগমেন্ট ট্রি তে আমরা মূল অ্যারের বর্তমান অবস্থা কি সেটার হিসাব রাখবো। অর্থাৎ, মূল অ্যারের কোন ইনডেক্সের ভ্যালু বর্তমানে কত সেটা জানবো। এবং রেঞ্জ আপডেট করবো। 

২) এরপর, আমরা মূল অ্যারের জন্য একটি ডিফারেন্স অ্যারে তৈরী করবো। যেখানে,

    dif[i] = ara[i] - ara[i-1]

৩) ২য় সেগমেন্ট ট্রি মূলত ডিফারেন্স অ্যারের একটি সাবঅ্যারের GCD বের করে দিতে সাহায্য করবে আমাদের।

এখন, একটি বিষয় লক্ষ্য করা যাক তা হলো মনে করি l to r ইনডেক্সের ভ্যালু x বাড়াতে হবে। তাহলে ডিফারেন্স অ্যারে তে কি পরিবর্তন আসবে?  

dif[l] += x

dif[r+1] -= x

মানে ডিফারেন্স অ্যারে তে শুধু দুটি পয়েন্ট আপডেট করতে হবে। l তম ইনডেক্সের ভ্যালু x বাড়বে আর r+1 তম ইনডেক্সের ভ্যালু x কমবে। 

আশা করি, এখন প্রব্লেমটি সলভ করা সম্ভব। নিজে নিজে কোড করার চেষ্টা করেও ব্যার্থ হলে নিচে কোড দেখে নিতে পারো।

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define gcd(a,b) __gcd(a,b)
	#define sz 200009
	ll ara[sz];
	///Segment Tree for maintaining main given array
	ll lazy[4*sz],tree[4*sz];
	void push_down(ll node,ll b,ll e)
	{
	tree[node] += lazy[node];
	if(b != e){
	lazy[node<<1] += lazy[node];
	lazy[1+(node<<1)] += lazy[node];
	}
	lazy[node] = 0;
	}
	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] = max(tree[node<<1] , tree[1+(node<<1)]);
	}
	void Update(ll node,ll b,ll e,ll i,ll j,ll val)
	{
	if(lazy[node] != 0)
	push_down(node , b , e);
	if(e<i || b>j)
	return;
	if(b>=i && e<=j){
	tree[node] += val;
	if(b != e){
	lazy[node<<1] += val;
	lazy[1+(node<<1)] += val;
	}
	return;
	}
	ll mid = (b+e)>>1;
	Update(node<<1 , b , mid , i , j , val);
	Update(1+(node<<1) , mid+1 , e , i , j , val);
	tree[node] = max(tree[node<<1] , tree[1+(node<<1)]);
	}
	ll Query(ll node,ll b,ll e,ll i,ll j)
	{
	if(lazy[node] != 0)
	push_down(node , b , e);
	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 max(p1 , p2);
	}
	///Segment tree for maintaining difference array
	ll dif[sz],treegc[4*sz];
	void Build2(ll node,ll b,ll e)
	{
	if(b == e){
	treegc[node] = dif[b];
	return;
	}
	ll mid = (b+e)>>1;
	Build2(node<<1 , b , mid);
	Build2(1+(node<<1) , mid+1 , e);
	treegc[node] = gcd((ll)fabs(treegc[node<<1]) , (ll)fabs(treegc[1+(node<<1)]));
	}
	ll Query2(ll node,ll b,ll e,ll i,ll j)
	{
	if(e<i || b>j)
	return 0LL; ///Because GCD(0 , x) = x
	if(b>=i && e<=j)
	return fabs(treegc[node]);
	ll mid = (b+e)>>1;
	ll p1 = Query2(node<<1 , b , mid , i , j);
	ll p2 = Query2(1+(node<<1) , mid+1 , e , i , j);
	return gcd((ll)fabs(p1) , (ll)fabs(p2));
	}
	void Update2(ll node,ll b,ll e,ll pos,ll val) ///Point Update
	{
	if(e<pos || b>pos)
	return;
	if(b == pos && e == pos){
	treegc[node] += val;
	return;
	}
	ll mid = (b+e)>>1;
	Update2(node<<1 , b , mid , pos , val);
	Update2(1+(node<<1) , mid+1 , e , pos , val);
	treegc[node] = gcd((ll)fabs(treegc[node<<1]) , (ll)fabs(treegc[1+(node<<1)]));
	}
	void Solve()
	{
	ll i,j,k,n,l,r,x,q,type;
	cin>>n>>q;
	for(i=1 ; i<=n ; i++){
	cin>>ara[i];
	dif[i] = ara[i] - ara[i-1];
	}
	Build(1 , 1 , n);
	Build2(1 , 1 , n);
	for(i=1 ; i<=q ; i++){
	cin>>type>>l>>r;
	if(type == 1){
	ll al = Query(1 , 1 , n , l , r) , gc = 0LL;
	if(l < r)
	gc = Query2(1 , 1 , n , l+1 , r);
	gc = gcd(gc , al);
	cout<<gc<<endl;
	}
	else{
	cin>>x;
	///Update main array
	Update(1 , 1 , n , l , r , x);
	///Update difference array
	Update2(1 , 1 , n , l , x);
	if(r+1 <= n)
	Update2(1 , 1 , n , r+1 , -x);
	}
	}
	}
	int main()
	{
	Solve();
	return 0;
	}

view raw Range GCD with Range Update.cpp hosted with ❤ by GitHub

Click here to solve similar problem

Happy Coding