এই সমস্যায়, আমাদেরকে N এবং Q প্রশ্নগুলির একটি অ্যারে অ্যারে [] দেওয়া হয়েছে যা দুই ধরনের হতে পারে। আমাদের কাজ হল একটি প্রদত্ত সূচক আপডেট করতে এবং পরিসরে GCD খুঁজে বের করার জন্য প্রশ্নের সমাধান করার জন্য একটি প্রোগ্রাম তৈরি করা৷
প্রশ্নগুলি হল −
টাইপ 1 − {1, index, value} - মান দ্বারা প্রদত্ত সূচকে উপাদান বাড়ান।
টাইপ 2৷ − {2, L, R} - সূচক পরিসরে উপাদানগুলির GCD খুঁজুন [L, R]৷
সমস্যা বর্ণনা − আমাদের [L, R] পরিসরে থাকা উপাদানগুলির GCD খুঁজে বের করতে হবে এবং মান ফেরত দিতে হবে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {5, 1, 7, 3, 8}, Q = 3
Queries: {{2, 2 , 5}, {1, 3, 6}, {2, 2, 5}} আউটপুট
ব্যাখ্যা
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি পন্থা হল সেগমেন্ট ট্রি ব্যবহার করা যা অ্যারেগুলির জন্য GCD এর প্রিপ্রসেস করতে ব্যবহৃত হয়। এটি প্রতিটি প্রশ্নের জন্য GCD কম্পিউট করার সময় কমিয়ে দেবে।
সেগমেন্ট ট্রি তৈরি করা এবং কাজ করা
আমরা এখানে যে সেগমেন্ট ট্রি ব্যবহার করছি তা হল একটি গাছ যা অ্যারের উপাদানগুলিকে লিফ নোড হিসাবে এবং উপাদানগুলির GCD অভ্যন্তরীণ নোড হিসাবে সংরক্ষণ করে৷
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
int calcGcdRangeRec(int* st, int segL, int segR, int L, int R, int currNode) {
if (L <= segL && R >= segR)
return st[currNode];
if (segR < L || segL > R)
return 0;
int mid = (segL + (segR - segL)/2);
int GcdL = calcGcdRangeRec(st, segL, mid, L, R, 2 * currNode + 1) ;
int GcdR = calcGcdRangeRec(st, mid + 1, segR, L, R, 2 * currNode + 2);
return __gcd(GcdL, GcdR);
}
void updateArrayValueRec(int* st, int L, int R, int index, int diff, int currNode) {
if (index < L || index > R)
return;
st[currNode] = st[currNode] + diff;
if (R != L) {
int mid = (L + (R - L)/ 2);
updateArrayValueRec(st, L, mid, index, diff, 2 * currNode + 1);
updateArrayValueRec(st, mid + 1, R, index, diff, 2 * currNode + 2);
}
}
void updateArrayValue(int arr[], int* st, int n, int index, int newVal) {
if (index < 0 || index > n - 1)
cout << "Invalid Input";
else{
int diff = newVal - arr[index];
arr[index] = newVal;
updateArrayValueRec(st, 0, n - 1, index, diff, 0);
}
}
int calcGcdRange(int* st, int n, int L, int R) {
if (L < 0 || R > n - 1 || L > R) {
cout << "Invalid Input";
return -1;
}
return calcGcdRangeRec(st, 0, n - 1, L, R, 0);
}
int constructGcdST(int arr[], int L, int R, int* st, int currNode) {
if (L == R) {
st[currNode] = arr[L];
return arr[L];
}
int mid = (L + (R - L)/2);
int GcdL = constructGcdST(arr, L, mid, st, currNode * 2 + 1);
int GcdR = constructGcdST(arr, mid + 1, R, st, currNode * 2 + 2);
st[currNode] = __gcd(GcdL, GcdR);
return st[currNode];
}
int main() {
int arr[] = { 1, 3, 6, 9, 9, 11 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[3][3] = {{2, 1, 3}, {1, 1 , 10}, {2, 1, 3}};
int value = (int)(ceil(log2(n)));
int size = 2 * (int)pow(2, value) - 1;
int* st = new int[size];
constructGcdST(arr, 0, n - 1, st, 0);
for(int i = 0; i < n; i++){
if(query[i][0] == 1){
cout<<"Query "<<(i + 1)<<": Updating Values!\n";
updateArrayValue(arr, st, n, query[i][1], query[i][2]);
}
if(query[i][0] == 2)
cout<<"Query "<<(i + 1)<<": GCD is "<<calcGcdRange(st, n, query[i][1], query[i][2])<<endl;
}
return 0;
} ইনপুট
Query 1: GCD is 3 Query 2: Updating Values! Query 3: GCD is 1
