خب این سوال هم یکی از سوالات آزمون آزمایشی های همیشگی دوره بوده لینکش تو ادامه مطلب هست
حل سوال هم همینطور...
خب لینک سوال اینه
راه حل :
سوال رو با segment tree + lazy حل می کنیم فرض کنید سوال از ما می خواد به جای اینکه به بازه ی L تا R به ترتیب 1 , 2 , ... , (R - L + 1) را اضافه کنیم تو بازه ی L تا R هر عدد را با اندیسش جمع کنیم، برای اینکه این کارو انجام بدیم تو هر query هر بار که به یک راس سگمنت میرسیم که داخل بازه بود مقدار lazy اونو با (sum(a,b جمع می زنیم (بازه راس سگمنت از a تا b ئه) برای update کردن مقدار خود راس سگمنت هم کافیه که اونو با مقدار lazy خودش جمع کنیم و در آخر lazy یشو ۰ کنیم. اینطوری مقدار خونه های L تا R را با اندیسشون جمع زدیم دیگه حالا برای تبدیل کردنش به مساله اصلی کافیه از بازه L تا R عدد (1 - L) را کم کنیم که با استفاده از lazy بدیهی حله و تمامه کار.
اینم کدش :
دریافت
