سوال خوبی بود فقط جاج نداشتم .

برام تستر بنویسی ممنون میشم.

کدش

یکمم توضیح برای افزایش رضایت مندی :)

اول برحسب x ها sort کردمو که بتونم swipe line بزنم بعدش توی سگمنت یه خونه دارم که ارزش مزرعه ای که این گوشه چپ پایینشه .

بعد swipe line رو اینطور می زنم که الان از بازه ی k تا k +p دارم یعنی بعدش می شه k+1 و k+p+1 بعد تمامم الماس هارو روبازه ای که شامل این خونه میشوند(این تو معدشون قرار داره ) اضافه می کنند:

بعدش توی segment tree ماکسیمم رو هم دارم و بعد از این که swipe line ام یه دونه رفت جلو با ماکسمم جواب ماکسیمم می گیرم دقت کنید که اگه lazy نمیزدم تایم میشدم

در ضمن به ازای هر الماس(با ارزش +1) q تا جلوتر یه خونه با ارزش -1 گذاشتم که وقتی که الماسه رفت بیرون منفی اش میاد تو :|

بهتون پیشنهاد می کنم که حتما یه بار خودتون بزنید هم segment tree Lazy داره هم swipe line.

واقعن سوال خوبی بود. کد من رو هم تست کنی ممنون میشم!
راه حل همون راه تاکسیران هست ... فقط $nlgn$ هست و $lazy$ نداره.

برای اینکه راه بشه $nlgn$ و مستقل از مختصات ها بشه, اینکارو میکنیم : قبول دارین کلن $n$ تا $x$ داریم که تو کل برنامه ازشون استفاده میکنیم؟ (و همچنین $n$ تا $y$) $x$ ها رو میشه همون کاری که تاکسیران کرد (نقاط رو بر حسب $x$ سورت کنیم و بر حسب اون دونه دونه اضافه و حذف کنیم) $O(N)$ کرد. برای $y$ ها هم میتونیم همه ی این $y$ های بدرد بخور رو تو یه آرایه بریزیم و سورت کنیم و یونیک کنیم (عناصر تکراری رو حذف کنیم). برای کار با این خونه ها, هر وقت خونه ای با مختصات $y$ رو کار داشتیم کافیه رو اون آرایه هه باینری سرچ بزنیم تا پیداش کنیم!

ما برای انجام دادن این دو تا کار از سگمنت تری استفاده میکنیم : ۱. به تمامی اعضای بازه ی $[l, r)$ , مقدار $val$ رو اضافه کن. و ۲. بزرگترین عضو آرایه ؟
برای هر راس سگمنت تری, دو تا عدد نگه میداریم : مجموع $val$ هایی که به کل بازه اش اضافه کردیم و بزرگترین عضو در بین زیر درختش بجز خودش. بزرگی این راس هم میشه مجموع این دو تا عدداش. برای کار نوع ۱ کافیه عدد اولی بازه های لازم رو بروز کنیم و عدد دوم اجدادشون رو بروز کنیم و برای کار نوع ۲ هم بزرگی ریشه ی درخت رو خروجی بدیم! $^_^$

پی نوشت: دوستانی که با سگمنت تری و یا سویپلاین آشنایی کامل ندارن این ها منابع خوبی هستن :
سگمنت تری - کاهو
سویپ لاین - تاپکدر