এই সমস্যাটিতে, আমাদেরকে একটি সংখ্যা দেওয়া হয়েছে যা একটি অ্যারের আকার যা সমস্ত শূন্য এবং Q প্রশ্নগুলি নিম্নলিখিত প্রকারের প্রত্যেকটি নিয়ে গঠিত -
update(s, e, val ) -> এই ক্যোয়ারীটি s থেকে e (উভয়ই অন্তর্ভুক্ত) থেকে val-এ সমস্ত উপাদান আপডেট করবে৷
আমাদের কাজ হল প্রদত্ত অপারেশন q বার প্রয়োগ করার পরে অ্যারেতে বিভিন্ন সংখ্যার সংখ্যা খুঁজে বের করা
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
Input : N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) Output : 2
ব্যাখ্যা
প্রাথমিক অ্যারে, অ্যার[] ={0, 0, 0, 0, 0, 0}
প্রশ্ন 1 − update(1, 4, 3) -> arr[] ={0, 3, 3, 3, 3, 0}
প্রশ্ন 2 − update(0, 2, 4) -> arr[] ={4, 4, 4, 3, 3, 0}
সমাধান পদ্ধতি
সমস্যার একটি সহজ সমাধান হল অ্যারেতে প্রতিটি ক্যোয়ারী সম্পাদন করা এবং তারপর অ্যারের অনন্য মানের সংখ্যা গণনা করা এবং একটি অতিরিক্ত অ্যারে ব্যবহার করা। এবং তারপর অনন্য অ্যারের গণনা ফেরত দিন।
এই সমাধানটি ভাল কিন্তু সমস্যাটির আরও কার্যকরী সমাধান হল অলস প্রচার ধারণাটি ব্যবহার করে ক্যোয়ারীতে সম্পাদিত রেঞ্জ অপারেশন অপ্টিমাইজ করতে। অ্যারেতে অনন্য সংখ্যার সংখ্যা খুঁজে পেতে আমরা কোয়েরি অপারেশনে অলস প্রচার কল ব্যবহার করব। এর জন্য আমরা একটি সেগমেন্ট ট্রি নেব এবং অপারেশনটি চালানো হলে নোড আপডেট করব এবং 0 দিয়ে ট্রি শুরু করব, অপারেশনে আপডেট হওয়া মানগুলি কাঙ্খিত মান প্রদান করবে। এখানে একটি প্রোগ্রাম যা সমাধানটি আরও ভালভাবে ব্যাখ্যা করবে৷
৷উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
#define N 100005
int lazyST[4 * N];
set<int> diffNo;
void update(int s, int e, int val, int idx, int l, int r){
if (s >= r or l >= e)
return;
if (s <= l && r <= e) {
lazyST[idx] = val;
return;
}
int mid = (l + r) / 2;
if (lazyST[idx])
lazyST[2 * idx] = lazyST[2 * idx + 1] = lazyST[idx];
lazyST[idx] = 0;
update(s, e, val, 2 * idx, l, mid);
update(s, e, val, 2 * idx + 1, mid, r);
}
void query(int idx, int l, int r){
if (lazyST[idx]) {
diffNo.insert(lazyST[idx]);
return;
}
if (r - l < 2)
return;
int mid = (l + r) / 2;
query(2 * idx, l, mid);
query(2 * idx + 1, mid, r);
}
int main() {
int n = 6, q = 3;
update(1, 3, 5, 1, 0, n);
update(4, 5, 1, 1, 0, n);
update(0, 2, 9, 1, 0, n);
query(1, 0, n);
cout<<"The number of different numbers in the array after operation is "<<diffNo.size();
return 0;
} আউটপুট
The number of different numbers in the array after operation is 3
