Count the Deliveries

সাবটাস্ক 1:

প্রথম সাবটাস্ক এর জন্য আমরা প্রতিটা রেকর্ড সিমুলেট করতে পারি, কারণ, অর্ডার পরিমাণ বাড়ে একজনের, অর্ডার করেও একজন।

সাবটাস্ক 2:

দ্বিতীয় সাবটাস্ক এ আমরা একটি সেগমেন্ট ট্রি তে আমরা সকল অর্ডার গুলো রাখতে পারি। অর্থাৎ প্রত্যেক কাস্টোমারের জন্য আমরা সেগমেন্ট ট্রি এর মাধ্যমে হিসাব রাখবো সে কতবার অর্ডার করেছে। যখন কারো অর্ডার পরিমাণ পরিবর্তন হবে (যেটা এক রেকর্ডে শুধু একজনেরই হবে) তখন পুরনো পরিমাণ দিয়ে জমিয়ে রাখা অর্ডার গুলো করে দিব এবং অর্ডারের সংখ্যা ০ করে দিবো (যাতে নতুন পরিমাণ এর হিসাবে পুরনো অর্ডার গুলো না আসে)

সাবটাস্ক 3:

তৃতীয় সাবটাস্কের জন্যেও আমরা সেগমেন্ট ট্রি ব্যবহার করব, তবে এই সেগমেন্ট ট্রি তে প্রত্যেক ইন্ডেক্সে দুইটি সংখ্যা থাকবেঃ weight এবং value। এবং সেগমেন্ট ট্রি দিয়ে যেকোন রেঞ্জের প্রতি ইন্ডেক্সের $weight * value$ গুলোর যোগফল জানা যাবে। এখন আমরা যেটা করবো সব গুলো রেকর্ড আগে স্ক্যান করে নিব এরপর প্রত্যেক কাস্টোমারের জন্য উত্তর গুলো বের করবো। কিন্তু এটা করার সময় $q$ সাইজের সেগমেন্ট ট্রিটা মেইনটেইন করব। যদি $i$ তম রেকর্ডে $l$ থেকে $r$ কাস্টোমারের অর্ডার পরিমান $x$ করে বাড়ে তাহলে, $l$তম কাস্টোমার এর উত্তর বের করার আগে সেগমেন্ট ট্রি তে $i$ তম ইন্ডেক্স এ value $x$ পরিমাণ বৃদ্ধি করবো এবং $r+1$ তম কাস্টোমার এর উত্তর বের করার আগে $i$ তম ইন্ডেক্সে value $x$ পরিমাণ কমিয়ে নিব। আবার যদি $j$ তম রেকর্ডে $l$ থেকে $r$ কাস্টোমাররা $x$ বার অর্ডার করে তাহলে $l$ তম কাস্টোমারের উত্তর বের করার আগে $1$ থেকে $j$ পর্যন্ত সবার weight $x$ পরিমাণ বৃদ্ধি করে দিব এবং $r+1$ তম কাস্টোমারের উত্তর বের করার আগে $1$ থেকে $j$ পর্যন্ত সবার weight $x$ পরিমাণ কমিয়ে দিব। এভাবে করলে একজন কাস্টোমারের উত্তর বের করার জন্য সেগমেন্ট ট্রি র সব ইন্ডেক্স এর $weight * value$ গুলোর যোগফল করলেই হবে।