Codeforces - 301D - Yaroslav and Divisors

Problem Description  Click Here

Topic Of This Problem: Segment Tree with Offline Query

n সংখ্যক ভিন্ন ভিন্ন সংখ্যার একটি অ্যারে দেয়া থাকবে এবং q সংখ্যক কুয়েরী দেয়া থাকবে। প্রতি কুয়েরী তে l থেকে r ইনডেক্সের মাঝে এমন কয়টা পেয়ার (ara[i] , ara[j]) আছে যেখানে ara[i] সংখ্যাটি ara[j] এর একটা ডিভিজর।

প্রথমে এই প্রব্লেমটাকে একটু জেনারেলাইজ করা যাক, তোমাকে একটা দ্বিমাত্রিক তল দেয়া আছে। এই তলে অনেকগুলো অনুভূমিক রেখা আছে। বের করতে হবে, X অক্ষ বরাবর l to r ইনডেক্সের মাঝে কয়টা রেখা সম্পূর্ণভাবে অবস্থান করে।

সল্যুশন আইডিয়াঃ

১) জেনারেলাইজ প্রব্লেম অনুযায়ী, প্রতিটা অনুভূমিক রেখার স্টার্টিং আর এন্ডিং পয়েন্ট আমার জানা লাগবে। এজন্য, ১ থেকে n পর্যন্ত প্রতিটি সংখ্যার জন্য তার মাল্টিপল এর ইনডেক্স বের করবো। যেমন, ২ এর ইনডেক্স যদি x হয় এবং ৪ এর ইনডেক্স যদি y হয় তার মানে অনুভূমিক রেখাটি X অক্ষের সমান্তরালে x থেকে y পর্যন্ত অবস্থিত। এভাবে, প্রতিটি সংখ্যার ইনডেক্স এর জন্য তার মাল্টিপলগুলোর ইনডেক্স গুলো বের করে রাখবো।

২) এবার কুয়েরী ইনপুট নেয়ার সময় একটি পেয়ার এর ভেক্টরে প্রত্যেক পজিশন থেকে শুরু হওয়া সেগমেন্ট এর {r , queryid} এর পেয়ার স্টোর করবো। মানে, qry[l].push_back({r , queryid}). 

৩) এখন, n to 1 পর্যন্ত লুপ ঘুরাবো। এবং প্রতি পজিশন i এ দাঁড়িয়ে, ara[i] এর মাল্টিপলগুলোর id এর জন্য সেগমেন্ট ট্রি তে ভ্যালু ১ করে বাড়াবো (পয়েন্ট আপডেট)। শুরুতে সেগমেন্ট ট্রি এর প্রতি পজিশনের ভ্যালু ০ ছিলো।

এবার, যেসব কুয়েরীর লেফট i থেকে শুরু সেসব কুয়েরীর জন্য সেগমেন্ট ট্রি এর সাম কুয়েরী কে কল দিয়ে তার এন্সার বের করি এবং কুয়েরী আইডি অনুসারে সেইভ রাখি।

৪) সবশেষে, কুয়েরী গুলোর এন্সার প্রিন্ট করে দেই আইডি ১ থেকে q পর্যন্ত। 

অফলাইন কুয়েরী মানেই হলো, প্রব্লেম সলভ করার সুবিধার্থে কুয়েরীগুলোর এন্সার সিরিয়ালি বের না করে উলটাপালটা যখন যেটা সুবিধা হয় সেটা বের করে নেয়া। এবং কুয়েরী টার সিরিয়াল নম্বর দেখে সেটা সেইভ করে রাখা। সবগুলো কুয়েরীর এন্সার বের করা হয়ে গেলে এবার সেগুলো সিরিয়ালি প্রিন্ট করে দেয়া। 

অফলাইন কুয়েরী বোঝার জন্য এটি একটি ভালো প্রব্লেম এবং আশা করি টিউটরিয়ালটিও সহায়ক হবে।

সেগমেন্ট ট্রি সম্পর্কে জানতে ক্লিক করুন

Happy Coding -_-