محاصره (Siege)

چنگیزخان با ارتش عظیمش بار دیگر در فکر حمله به چین است و در پی این تصمیم به سربازانش دستور داده است که $n$ نردبان با $h$ پله پای دیوار بزرگ چین بگذارند. می‌دانیم سربازان چنگیز اگر روی نردبانی باشند هر ثانیه دقیقا ۱ پله بالا می‌روند. همچنین هر ثانیه‌یکی از دو اتفاق زیر رخ می‌دهد:

چنگیز به سربازانش دستور می‌دهد که به ازای نردبان‌های $l$ام تا $r$ام از هر نردبان دقیقا $x$ نفر همزمان شروع به بالا رفتن بکنند.
اینکه سربازان چینی از بالای دیوار سنگی بر روی نردبان $i$ام می‌اندازند که $k$ نفر بالایی نردبان را می‌کشد. دقت کنید که اگر کمتر از $k$ نفر روی نردبان باشند، سنگ تمام افراد روی نردبان را می‌کشد و سپس بدون آسیب دیگری به زمین می‌رسد.

این حمله برای $q$ ثانیه اتفاق جدید دارد. بعد از آن هم چنگیز صدایش می‌گیرد و دستور دیگری نمی‌دهد. البته سربازان چینی نیز دیگر سنگی ندارند. سربازان مغولی که روی نردبان‌ها هستند از ترس چنگیز همچنان به بالا رفتن ادامه می‌دهند. برای درک بیشتر سوال به مثال‌ها توجه کنید.

در پایان، چنگیز که از حساب و کتاب بدش می‌آید، از شما میخواهد به او کمک کنید که بداند چند تن از سربازانش به بالای نردبان‌ها رسیده‌اند.

ورودی

در خط اول به ترتیب $n$ و $q$ و $h$ می‌آیند که نشان‌دهنده تعداد نردبان‌ها، تعداد اتفاقات و تعداد پله‌های نردبان‌ها هستند.

در ادامه $q$ خط داده می‌شوند که هر یک یکی از دو حالت زیر را دارند.

$\texttt{1} \quad l \quad r \quad x$: که نشان‌دهنده اتفاق نوع اول است و یا
$\texttt{2} \quad i \quad k$: که نشان‌دهنده اتفاق نوع دوم است.

خروجی

در تنها خط خروجی بگویید که چند سرباز چنگیز بعد از $10^{18}$ ثانیه به بالای نردبان‌ها می‌رسند.

زیرمسئله‌ها

زیرمسئله اول (۷ نمره): $1 \leq n, q \leq 2000$
زیرمسئله دوم (۱۲ نمره): $1 \leq h \leq 200$
زیرمسئله سوم (۳۸ نمره): $x, k = 1$
زیرمسئله چهارم (۴۳ نمره): بدون محدودیت اضافی

محدودیت‌ها

$1 \leq n\, , \, q \leq 200000$
$1 \leq h \leq 10^9$
$1 \leq l \leq r \leq n$
$1 \leq i \leq n$
$1 \leq k\, , \, x \leq 10^7$

ورودی و خروجی نمونه

ورودی نمونه	خروجی نمونه
3 3 1 1 1 2 1 2 1 1 2 2 1	1
5 6 3 2 4 5 1 1 5 2 1 1 3 1 2 4 3 1 1 1 9 2 5 2	20

شرح ورودی و خروجی نمونه

در ورودی نمونه اول؛

در ثانیه‌ی اول دو سرباز یکی از نردبان اول و دیگری از نردبان دوم شروع به بالا رفتن می‌کنند.
در ثانیه‌ی دوم یک سنگ روی نردبان اول انداخته می‌شود که‌یک سرباز را می‌کشد.
در ثانیه سوم یک سنگ روی نردبان دوم انداخته می‌شود که کسی را نمی‌کشد زیرا سربازی که روی نردبان دوم بوده، قبلاً به بالای دیوار چین رسیده‌است.

راهنمایی

اگر برای هر سنگ تعداد افرادی که آن سنگ می‌کشد را به دست بیاوریم، تعداد افرادی که به بالای نردبان‌ها می‌رسند برابر با تعداد کل افرادی که شروع به بالا رفتن از نردبان ها کرده‌اند منهای مجموع تعداد افرادی است که سنگ‌ها می‌کشند.

راهنمایی

فرض کنید افرادی که از یک نردبان بالا می‌روند را به ترتیب بالا رفتن شماره گذاری کرده‌ایم. (شخصی که زودتر از همه وارد شده با شماره ۱ شماره گذاری می‌کنیم و ترتیب شماره گذاری افرادی که در یک زمان شروع به بالا رفتن از نردبان می‌کنند را به ترتیب دلخواه تایین می‌کنیم.) در این صورت اگر در هر لحظه مانند $t$ شماره آخرین فردی که تا این لحظه روی نردبان $i$ کشته شده است را برابر با $last[i]$ قرار دهیم (در صورتی که کسی کشته نشده باشد $last[i]$ برابر صفر خواهد بود) آنگاه می‌دانیم دراین لحظه کمترین شماره بین افراد زنده روی نردبان $i$ که هنوز به بالای نردبان نرسیده‌اند برابر با بیشینه مقدار $last[i]+1$ و شماره اولین فردی که بعد از لحظه $t-h$ شروع به بالا رفتن از نردبان $i$ کرده است، می‌باشد. فرض کنید این مقدار برابر با $mn$ باشد.

راهنمایی

فرض کنید شماره آخرین فردی که قبل از لحظه $t$ شروع به بالا رفتن از نردبان $i$ کرده باشد $mx$ باشد. آنگاه اگر در لحظه $t$ سنگی روی نردبان $i$ پرتاب شود، تعداد افرادی که این سنگ می‌کشد برابر با $v = min(k, mx - mn + 1)$ خواهد بود و شماره آخرین فردی که کشته می‌شود برابر با $mn - v + 1$ خواهد بود.

راهنمایی

برای سنگ ها به ترتیب شماره نردبان (از کوچک به بزرگ) تعداد افرادی که می‌کشند را حساب کنید.

راهنمایی

فرض کنید آرایه $add$ را برای هر نردبان مانند $i$ طوری تعریف کرده باشیم که اگر در لحظه $t$، تعداد $x$ نفر شروع به بالا رفتن از نردبان $i$ کنند مقدار $add[t]$ برابر با $x$ و در غیر این صورت مقدار $add[t]$ برابر با صفر باشد. آنگاه شماره اولین فردی که بعد از لحظه $t$ شروع به بالا رفتن از نردبان کرده است(در صورت وجود) برابر با ۱ واحد بیشتر از مجموع تمام $add[i]$ ها به ازای $i<t$ است. همچنین شماره آخرین فردی که قبل از لحظه $t$ شروع به بالا رفتن از نردبان کرده است برابر با مجموع $add[i]$ ها برای$i<t$ است.

راهنمایی

اگر سنگ هایی که روی نردبان $i$ انداخته می‌شود را به ترتیب زمان پیمایش کنیم، با کمک آرایه $add$ (که در راهنمایی ۵ تعریف شده است) می‌توانیم با کمک درخت بازه‌ای $(segment \> tree)$ تعداد افرادی که این سنگ می‌کشد را در $O(\log{n})$ به دست بیاوریم و مقدار $last[i]$ را بازمحاسبه کنیم.

راهنمایی

وقتی کارمان با سنگ $i$ تمام شد و قصد داشتیم آرایه $add$ را برای سنگ $i+1$ بسازیم، نیاز به ساختن آرایه از اول نیست. صرفا اندیس هایی از آرایه که در سنگ $i$ و $i+1$ متفاوت است را تغییر می‌دهیم. هر پرسش از نوع اول نهایتا ۲ واحد به مجموع تغییرات اضافه می‌کند در نتیجه مجموع تغییرات از $O(q)$ خواهد بود.