Hououin Kyouma!

সাবটাস্ক ১ঃ
সবসময় $Q >= T$ এখানে । তাই প্রথমে $T$ টা প্রশ্ন করে কোন কোন ঘণ্টায় ক্লাস এবং কোন কোন ঘণ্টায় ক্লাস নেই, তা বের করে ফেলা যাবে । এরপর একটি লিনিয়ার লুপ চালিয়েই রেজাল্ট বের করা যাবে ।

সাবটাস্ক ২ঃ
ক্লাস টাইমের মত ফ্রী টাইমেরও $[t_1, t_2]$ রেঞ্জ আছে বলে ধরা যায়, যেখানে ফ্রী টাইম $t_1$-তম ঘণ্টা থেকে শুরু হয়ে $t_2$-তম ঘণ্টায় শেষ হয় । আমরা যদি এরকম সব ফ্রী টাইমের রেঞ্জ বের করতে পারি, তাহলে তাদের মাঝে যে রেঞ্জের দৈর্ঘ্য সর্বাধিক, সেই দৈর্ঘ্যই আমাদের রেজাল্ট ।

প্রোপার্টি ১ঃ যদি $[l, r]$ রেঞ্জের সম্পূর্ণ সময়ে ক্লাস না থাকে, তাহলে এই রেঞ্জের ফ্রী টাইম হবে $= (r-l+1)$ ঘণ্টা ।
প্রোপার্টি ২ঃ $[l, r]$ রেঞ্জের সম্পূর্ণ সময়ে যদি ক্লাস থাকে, তাহলে এই রেঞ্জের ফ্রী টাইম হবে $= 0$ ঘণ্টা ।

এখন আমরা আমরা যদি কোনো সময় $t_i$-তম ঘণ্টায় থাকি এবং সেটি ক্লাস টাইম হয়, তাহলে প্রোপার্টি ২ ব্যবহার করে বাইনারী সার্চ চালিয়ে এই ক্লাস কত তম ঘণ্টায় শেষ হয়, সেটা খুব সহজেই বের করে ফেলা যায় । ক্লাস টাইম যততম ঘণ্টায় শেষ, ঠিক টার পরের ঘণ্টাই ফ্রি টাইম হবে ।
$t_i$-তম ঘণ্টা ফ্রী টাইম হলে কী করতে হত, সেটা হোমটাস্ক ;) ।

এভাবে আমরা খুব সহজেই বাইনারী সার্চের মাধ্যমে $1^{st}$ ঘণ্টা থেকে $T$ পর্যন্ত ক্লাস টাইম, ফ্রী টাইমের সব রেঞ্জ বের করে ফেলতে পারব । যেহেতু, প্রতি ক্লাসের শুরু এবং শেষ ঘণ্টা বের করতে বাইনারী সার্চ লাগছে, তাই সর্বমোট প্রশ্ন দরকার হবে $ \leq 2\times N\times log_2(T)$, যা $5\times 10^4$ এর প্রশ্নসীমায় হয়ে যায় ।

সাবটাস্ক ৩ঃ
সাবটাস্ক ৩ এর সলিউশন মূলত সাবটাস্ক ২ এর সলিউশনের অপটিমাইজেশন । সাবটাস্ক ২ এ আমরা যখন বাইনারী সার্চ চালাচ্ছিলাম, তখন এক বাইনারী সার্চ থেকে পাওয়া ইনফর্মেশন আমরা কিন্তু অন্য কোনো বাইনারী সার্চে কাজে লাগাইনি । এখন আমরা এটি কাজে লাগাব । এই সাবটাস্কে আমরা সব প্রশ্ন $[1, t]$ এই ফরম্যাটে করব অর্থাৎ, $1^{st}$ ঘণ্টা থেকে $t$-তম ঘণ্টা পর্যন্ত টোটাল ফ্রী টাইম কত - সেটা জিজ্ঞাসা করব । এর কারণ একটু পরেই আমারা বুঝতে পারব ।

প্রোপার্টি ৩ঃ $[1, t_1-1]$ রেঞ্জে টোটাল ফ্রী টাইম $T_1$ ঘণ্টা এবং $[1, t_2]$ রেঞ্জে টোটাল ফ্রী টাইম $T_2$ ঘণ্টা হলে $[t_1, t_2]$ রেঞ্জে টোটাল ফ্রী টাইম $(T_2-T_1)$ ঘণ্টা, যেখানে $1 < t_1 \leq t_2 \leq T$ ।

ধরা যাক, $1^{st}$ ঘণ্টা থেকে ক্লাস টাইম, ফ্রী টাইম বের করতে করতে আমরা এখন $t_i$-তম ঘণ্টায় আছি । তার মানে $[1, t_i-1]$পর্যন্ত টোটাল ফ্রী টাইম কত, সেটাও আমাদের জানাই আছে ।

ধরি, $t_i$-তম ঘন্টাটি ফ্রী টাইম এবং আগের কোনো এক বাইনারী সার্চ থেকে $[1, t_j]$ রেঞ্জের টোটাল ফ্রী টাইম কত সেটা বের করা আছে, যেখানে $t_j > t_i$ । তাহলে প্রোপার্টি ৩ ব্যবহার করে কোনো এক্সট্রা প্রশ্ন জিজ্ঞাসা না করেই $[t_i, t_j]$ রেঞ্জের ফ্রী টাইম কত, সেটা আমরা বের করে ফেলতে পারব ।

এই ফ্রী টাইম যদি $(t_j-t_i+1)$ হয়, তার মানে $[t_i, t_j]$ রেঞ্জের পুরোটাই ফ্রী টাইম এবং এতে করে আমরা $t_j$-তম ঘণ্টার পর কোথায় ফ্রী টাইম শেষ হয়, সেটা খুঁজতে পারি । আর যদি ফ্রী টাইম $(t_j-t_i+1)$ না হয়, তার মানে $[t_i, t_j]$ রেঞ্জের মাঝেই কোথাও ক্লাস টাইম আছে । অর্থাৎ, $t_i$-তম ঘন্টায় থাকা ফ্রী টাইম $[t_i, t_j]$ রেঞ্জের কোনো এক ঘণ্টাতেই শেষ হবে । তাই আমরা এই রেঞ্জের ভিতরেই সেই শেষ ঘণ্টা খুঁজব ।
$t_i$-তম ঘন্টাটি ক্লাস টাইম হলে কী করতে হত, সেটা হোমটাস্ক :D ।

এভাবে আগের বাইনারী সার্চ থেকে পাওয়া ইনফর্মেশন কাজে লাগিয়ে আমরা পরবর্তী বাইনারী সার্চ চালানোর রেঞ্জগুলো ছোট করে ফেলতে পারি । এখন প্রশ্ন হচ্ছে, টোটাল প্রশ্নের সংখ্যা এভাবে কত কমবে?

প্রথমে $1_{st}$ ঘণ্টা থেকে প্রথম ক্লাস কততম ঘণ্টায় শুরু হয়, সেটা বের করতে $\log_2(T)$ সংখ্যক প্রশ্ন লাগবে । এরপর উপরের নিয়মে রেঞ্জ ছোট করার পর বাইনারী সার্চ চালাতে হবে এমন সবচেয়ে বড় রেঞ্জের দৈর্ঘ্য হবে $\frac{T}{2}$ । এমন দৈর্ঘ্যের রেঞ্জ ম্যাক্সিমাম $2$টা হওয়া সম্ভব (কারণ $2 \times \frac{T}{2} = T$) । তাহলে, আরও $2\times \log_2(\frac{T}{2})$ সংখ্যক প্রশ্ন লাগবে । এভাবে এগোতে থাকলে দেখা যায়, টোটাল প্রশ্নের সংখ্যা = $\log_2(T)+2\times \log_2(\frac{T}{2})+4\times \log_2(\frac{T}{4})+.....+k\times \log_2(\frac{T}{k})$, যেখানে $k = ceil(\log_2(2\times N))$ ।

এই প্রয়োজনীয় প্রশ্নের সংখ্যা $4.3\times 10^4$ এর চেয়ে কম । আরও একুরেট ক্যালকুলেশন করলে দেখা যায়, প্রশ্নসংখ্যা কখনোই $41843$ এর বেশি দরকার হবে না, বরং কেয়ারফুল থাকলে আরও কম লাগবে ।

[বিঃদ্রঃ মডিফাইড স্পার্স সেগমেন্ট ট্রি ব্যবহার করেও এই প্রবলেম সলভ করা সম্ভব]