এই সমস্যায়, আমাদের একটি সংখ্যা N দেওয়া আছে যা একটি অ্যারেতার আকার যাতে সব শূন্য আছে এবং Q কোয়েরি দেওয়া আছে নিচের টাইপের −
update(s, e, val) -> এই কোয়েরিটি s থেকে e (দোনোই ইনক্লুসিভ) পর্যন্ত সব উপাদানকে val-এ আপডেট করবে।
আমাদের কাজ হল দেওয়া অপারেশন q বার প্রয়োগ করার পর অ্যারেতে আলাদা সংখ্যাগুলোর সংখ্যা বের করা।
উদাহরণ
সমস্যাটি বুঝতে একটি উদাহরণ নিই:
ইনপুট : N = 6, Q = 2 Q1 = update(1, 4, 3) Q2 = update(0, 2, 4) আউটপুট : 2
ব্যাখ্যা
প্রাথমিক অ্যারে, arr[] = {0, 0, 0, 0, 0, 0}
কোয়েরি ১ − update(1, 4, 3) -> arr[] = {0, 3, 3, 3, 3, 0}
কোয়েরি ২ − update(0, 2, 4) -> arr[] = {4, 4, 4, 3, 3, 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
