প্রব্লেম
ধরা যাক, আমাদের কাছে ara[5] সাইজের একটা এরে আছে। আগেই বলে রাখছি, এরে ইনডেক্স শুরু হবে $1$ থেকে, $0$ থেকে না। আমাদের এই এরেতে ৭ বার কুয়েরি করতে হবে [x, y] ইন্টার্ভালে। প্রতি কুয়েরিতে ওই ইন্টার্ভালের ইনডেক্সগুলোতে $2$ যোগ করতে হবে। কুয়েরি শেষে পরিবর্তিত array প্রিন্ট করতে হবে।
1
2
3
4
5
6
7
8
9
ara[5] = {2, 3, 7, 4, 10}; // array input
// 07 queries
1 5
2 4
5 5
2 5
3 4
1 3
3 5
Query 1~5 means add $2$ at array index starting from $1$ then $2, 3, 4$ and 5. Now array looks like ara[5] = {4, 5, 9, 6, 12}
Query 2~4 means add $2$ at array index starting from $2$ then $3$ and $4$. Now array increased to ara[5] = {4, 7, 11, 8, 12}
Repeat this process for other queries.
এই ধরনের সমস্যা সাধারনত সেগমেন্ট ট্রি(লেজি প্রপাগেশন) কিংবা বাইনারি ইনডেক্স ট্রি দিয়ে সলভ করা যায়, যার কমপ্লেক্সিটি $O(\log n)$। আমি যেই ট্রিক্সটা নিয়ে লিখছি সেটির কমপ্লেক্সিটি অবশ্য $O(n)$. তবে $2×10^5$ সাইজের ইনপুটের ক্ষেত্রে এটা ভালোভাবে কাজে দিবে আর ইমপ্লিমেন্ট করাও সোজা ।
সমাধান
মূল কথায় আসি। আমার ট্রিকস হলো কোন ইনডেক্স কতবার কুয়েরি করা হয়েছে সেটা হিসেব করে রাখা। উপরের কুয়েরির জন্য যার ফলাফল আসে –
ara index[1] কুয়েরি করা হয়ে $2$ বার
ara index[2] কুয়েরি করা হয়ে $4$ বার
ara index[3] কুয়েরি করা হয়ে $6$ বার
ara index[4] কুয়েরি করা হয়ে $5$ বার
ara index[5] কুয়েরি করা হয়ে $4$ বার
এইটুকু হিসেব করতে পারলেই কাজ প্রায় শেষ । এখন ara এর প্রতিটা ইনডেক্সের মানের সাথে ( কুয়েরির মান $X$ যে ভেল্যুটা যোগ করতে বলা হয়ে তার মান ) যোগ করলেই আপডেটেড ara পাওয়া যাবে।
আপডেটেড এরে ভেল্যুগুলো এমন হবে –
1
2
3
4
5
ara[1] = 2 + 2*2
ara[2] = 3 + 4*2
ara[3] = 7 + 6*2
ara[4] = 4 + 5*2
ara[5] = 10 + 4*2
কোডিং
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int i, q, n, x, y, ara[20010], v[20010], fr[20010];
int main()
{
//ara[5] = {2, 3, 7, 4, 10};
scanf(“%d %d”, &n, &q);
// input array values
for(i = 1; i <= n; i++) {
cin>>ara[i]; // 1 indexed
}
while(q–)
{
cin >> x >> y;
v[x] += 1;
v[y+1] -= 1;
}
for(i = 1; i <= n; i++) {
fr[i] = fr[i-1] + v[i];
printf(“index %d asks for %d timesn”, i, fr[i]);
}
//Updating new array
printf(“nNew array:”);
for(i = 1; i <= n; i++) {
ara[i] = ara[i] + fr[i]* 2;
printf(” %d”, ara[i]);
}
printf(“n”);
return 0;
}