پیش نیاز برای خوندن این راه حل دونستن انواع سگمنت تری و نحوه ی پیاده سازی اوناست ... از اینجا میتونین اینا رو یاد بگیرین! :)

اول کار دو تا سگمنت تری میسازیم ... $SGTMin$ و $SGTMax$ که وطیفه شان به ترتیب نگهداری مینیمم ارتفاع بازه ها و ماکزیمم ارتفاع بازه ها هست. اولش همه ی رئوس $SGTMax$ برابر $INF$ هستند و همه ی رئوس $SGTMin$ برابر 0.

در حالت کلی هر کدام از پرسش ها (کاهش یا افزایش) میاد برای بازه ی $[l, r]$ کمترین ارتفاع و یا بیشترین ارتفاع (و یا هردو) رو تغییر میده. بعبارت دیگه میاد ارتفاع ستون های$l$ تا $r$ رو از یک طرف محدود میکنه (که بزرگتر یا کوچکتر از $h$ باشند). پس ما میایم این پرسش ها رو اینجوری پیاده سازی میکنیم که :

کاهش :
برای کاهش ارتفاع ساختمان های بازه ی $[l, r]$ به $h$، ما به هر دو سگمنت تری بشکل سگمنت تری های نگهداری مینیمم نگاه میکنیم و آن دو رو آپدیت میکنیم ... یعنی اگر مقدار راسی که بازه ی متناظرش با بازه ی $[l, r]$ ورودی تداخل دارد از $h$ بزرگتر بود، اون مقدار رو $h=$ قرار میدهیم وگرنه تغییرش نمیدهیم. (در نگاه اول بنظر میرسه که تنها باید $SGTMax$ رو آپدیت کنیم ولی ممکنه که مقادیری در $SGTMin$ هم از $h$ بیشتر باشن.)

افزایش :
برای افزایش هم دقیقن مثل کاهش ولی به سگمنت تری ها مثل سگمنت تری های نگهداری ماکزیمم نگاه میکنیم و آپدیت میکنیم.

(این اعمال با استفاده از lazy propagation هر کدام $O(lgN)$ طول میکشند. دقت کنید که چون برای آپدیت هر درخت دو جور دستور مختلف داریم باید دو متغیر جدا برای lazy propagation در هر راس درخت نگه داریم.)

در آخر هم هر دو درخت رو بطور کامل پیمایش میکنیم و برای هر $1 \le i \le N$، $Min_i$ و $Max_i$ رو در میاریم که یعنی طی این عملیات های انجام شده $h_i$ از دو طرف به چه مقدارهایی محدود شده. سه حالت پیش میاد :
1) $Min_i \le h_i \le Max_i$ که یعنی در طی این اعمال $h_i$ تغییری نکرده و برابر با مقدار اولیش هست.
2) $h_i < Min_i$ که یعنی در مجموع عملیات ها $h_i$ بزرگتر شده و الان برابر $Min_i$ است.
3) $h_i > Max_i$ که یعنی در مجموع عملیات ها $h_i$ کوچکتر شده و الان برابر $Max_i$ هست.
این مرحله هم چون تمام رئوس سگمنت تری ها را میپیماید در کل $O(N)$ طول میکشه .

پس در کل پیچیدگی الگوریتم از $O(N + K lg N)$ هست! $^_^$