কয়েকটা উপায়ে এই প্রবলেমটির সমাধান করা যায়:
১. ইজি সাব-টাস্কের জন্য প্রতি কোয়েরির জন্য একটা লুপ দিয়ে কোয়েরির শুরু থেকে শেষ পর্যন্ত স্ক্যান করলেই হবে।
২. বাকেট সর্টের ধারণা ব্যবহার করে প্রতিটা সংখ্যা কোন কোন ইনডেক্সে এসেছে এটা একটা কন্টেইনারে সর্টেড করে রাখা যায়। তারপর ঐ নাম্বারের উপরে কোয়েরি আসলে সেই সর্টেড অ্যারের উপর বাইনারি সার্চ করা যায়।
৩. যেই অ্যারেটা দেওয়া থাকবে, সেটিকে স্কয়ার রুট N সংখ্যক ভাগে ভাগ করা যায়, যেখানে N হচ্ছে অ্যারেটির আসল সাইজ। প্রতিটা ভাগের জন্য একটি ম্যাপ রেখে প্রতি কোয়েরি স্কয়ার রুট N * লগ N কমপ্লেক্সিটিতে উত্তর দেওয়া যায়।
৪. সবগুলো কোয়েরি একবারে নিয়ে নেওয়া যায়, এরপর অফলাইনে সবগুলোকে প্রসেস করা যায়। এ ধরণের একটি প্রবলেম হচ্ছে “SPOJ Dquery”।
৫. মার্জ সর্ট ট্রি দিয়েও প্রবলেমটির সমাধান করা যায়।
Statistics
61%
Solution Ratio
Mr.HmianEarliest,
nusuBotFastest, 0.2s
nusuBotLightest, 6.9 MB
ITisMAHMUDShortest, 450B
