A Super Easy Problem - "Array Query"

সাবটাস্ক 1:
সাবটাস্ক 1 আমরা ব্রুটফোর্স করে সলভ করব। অর্থাৎ প্রতিটা কুয়েরির জন্য [L - R] সাব-সেগমেন্টের সব ইনডেক্স i এর জন্য রেজাল্টের সাথে |X - Ai| যোগ করব।
Time Complexity: প্রতিটা টেষ্টকেসের জন্য Time Complexity O(N × Q).
সাবটাস্ক 2:
সাবটাস্ক 2 তে অ্যরেতে সর্বোচ্চ 10 টা আলাদা ভ্যালু থাকবে। আমরা এই ভ্যালুগুলো নিয়ে কাজ করব। আমরা প্রতিটা আলাদা ভ্যালুর জন্য একটা ভেক্টর রাখব। ভেক্টরে ওই ভ্যালু যে ইনডেক্সে আছে সেই ইনডেক্সগুলো রাখব। প্রতিটা কুয়েরির জন্য একটা ভেক্টরে কতগুলো ইনডেক্স [L - R] সাব-সেগমেন্টের ভিতর আছে সেটা বের করব। এটা আমরা খুব সহজে বাইনারি সার্স করে বের করতে পারি। যদি এই ভ্যালু val হয় এবং এর কউন্টার cnt হয় তাহলে রেজাল্টের সাথে |X - val| × cnt যোগ করব। এই কাজটা প্রতিটা ভেক্টরের জন্য করতে হবে। ভ্যালুগুলো অনেক বড়, তাই কমপ্রেস করে কাজ করলে সুবিধা হবে।
Time Complexity: প্রতিটা টেষ্টকেসের জন্য Time Complexity O(Q × D × Log2N) যেখানে D = আলাদা ভ্যালুর সংখ্যা।
সাবটাস্ক 3:
সাবটাস্ক 3 সলভ করার জন্য আমাদের ডেটা-স্ট্রাকচার ব্যবহার করতে হবে। আমরা সেগমেন্ট ট্রী ব্যবহার করে প্রবলেমটি সলভ করব। প্রথমে আমরা একটি সেগমেন্ট ট্রী গঠন করব। সেগমেন্ট ট্রীর প্রতিটা নোডে থাকবে ২ টা ভেক্টর। প্রথম ভেক্টরে অ্যারের একটা নির্দিষ্ট রেঞ্জের (সেগমেন্ট ট্রীর বর্তমান রেঞ্জ) ভ্যালুগুলো সর্ট করে সাজানো থাকবে। এটাকে মার্জ সর্ট ট্রীও বলা হয়। দ্বিতীয় ভেক্টরে থাকবে প্রথম ভেক্টরের ভ্যালুগুলোর প্রিফিক্স সাম।
এখন আমরা এই ট্রী থেকে রেজাল্ট কিভাবে পেতে পারি সেটা দেখব। আমরা প্রতিটা কুয়েরির জন্য সেগমেন্ট ট্রীতে ট্রাভার্স করব। রুট নোড থেকে ট্রাভার্স করা শুরু করব এবং তার চাইল্ড নোড ধরে নিচে নামতে থাকব। যদি কোনো নোডের রেঞ্জ কুয়েরির রেঞ্জের ভিতরে থাকে আমরা ঐ নোডের উপর কাজ করব। ঐ নোডে যে ভেক্টরে ভ্যালুগুলো সর্ট করে রাখছি সেই ভেক্টরের কতগুলো ভ্যালু X এর চেয়ে ছোট এবং কতগুলো ভ্যালু X এর চেয়ে বড় সেটা বের করতে হবে। যেহেতু ভ্যালুগুলো সর্ট করা, তাই এটা বাইনারি সার্স করে বের করতে পারব। তারপর রেজাল্টের সাথে |Ps - X × S| + |Pb - X × B| যোগ করব এবং ওই নোড থেকে রিটার্ন করে দিব।
এখানে,
S = X এর চেয়ে ছোট ভ্যালুর সংখ্যা।
B = X এর চেয়ে বড় ভ্যালুর সংখ্যা।
Ps = X এর চেয়ে ছোট ভ্যালুগুলোর যোগফল।
Pb = X এর চেয়ে বড় ভ্যালুগুলোর যোগফল।

X এর চেয়ে ছোট এবং বড় ভ্যালুগুলোর যোগফল আমরা প্রিফিক্স সাম থেকে বের করব।

Time Complexity: প্রতিটা টেষ্টকেসের জন্য Time Complexity O(N × Log2N + Q × (Log2N)2).