یه کم زیاده، کم کم مینویسم که هینت هم باشه!

۱ـ میشه فرض کرد عددا از ۱ تا n+q هستن

۲ـ عددایی که به ۳ بخشپذیر نیستن، مهم نیستن پس به جاشون -۱ بذار. سوال میشه این: جمع اعداد نا منفی متمایز یه بازه چنده؟

۳ـ میشه دو بخش کرد ۲ رو. اول اینکه جمع اعداد نا منفی یه بازه رو بدست بیاریم، بعدش تکراری ها رو کم کنیم.

۴ـ بخش اول ۲ که بدیهیه

۵ـ برای بخش دوم: فرض کن k تا خونه آرایه برابر با x باشن. k - 1 تا بازه مینیمال بینشون وجود داره. به ازای هرکدوم این بازه ها که تو بازه [l, r] می افته، باید x تا از جواب کم کنیم.

۶ـ تعداد بازه هایی که تو ۵ بهشون اشاره کردیم، کلا از O(n+q) هست.

۷ـ یه دور برنامه رو ران کن، این بازه ها رو به ازای هر x در بیار. بعد برحسب L مرتبشون کن و یه سگمنت بساز که هر برگش، یه بازه برای یه x ای باشه.

۸ـ به ازای هر راس این سگمنته، یه فنویک بگیر که سایز اش برابر با تعداد برگ های زیرشه. بعد برگ های زیرش رو بر حسب R مرتب کن و هر خونه این فنویکه رو به یکیشون نسبت بده. خونه متناظر با بازه [l, r] و x برابر با ۰ هست اگر این بازه فعال نباشه. وگرنه برابر با x هست.

۹ـ حالا یه query رو که میخوای جواب بدی، جمع اعداد نامنفی بازشو حساب کن، بعد به ازای هر بازه ای که توی [l, r] می افته، مقداری که تو اون سگمنته بهش نسبت دادیم رو کم کن. چجوری؟ بازه ها تو اون سگمنته بر حسب L مرتب شدن، پس یه سری خونه متوالی تو اون سگمنته هستن که L اشون توی [l, r] می افته. برای یه راس سگمنت هم که میخوایم جواب بدیم، توی فنویک اون راس بازه ها بر حسب R مرتب شدن، L اشون هم که تو بازه [l, r] هست. پس از اول تا یه جایی از فنویکه، R بازه ها توی [l, r] هست. پس میشه جمعشون زد دیگه.

در کل تو اردر O(nlg^2) اجرا میشه. مموری هم از o(nlg)