- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
بعد از آنکه ابواسحاق از دست علف‌های هرز راحت شد، دشمنانش به دلیل موفقیتش در خیار کاری، به او حسادت کردند و تصمیم گرفتند یکی از مزارع او را تخریب کنند.
مزرعه ابواسحاق به صورت یک جدول $1 \times n$ است که خانه‌هایش از چپ به راست به ترتیب از ۱ تا $n$ شماره گذاری شده‌اند و در خانه $i$ اُم آن $ a_i $ خیار کاشته شده است. مزرعهٔ او $ q $ روز فعالیت می‌کند. در ابتدای هر روز، به تعداد خیارهای خانهٔ $i$ اُم $b_i$ تا اضافه می‌شود و در انتهای هر روز، یکی از دو اتفاق زیر رخ می‌دهد:
-
ابواسحاق نیاز به محاسبهٔ سود خود پیدا می‌کند و از شما مجموع تعداد خیارهای موجود در خانه‌های بازه‌ی $[l, r]$ را می‌پرسد.
-
دشمنان ابواسحاق خانهٔ $x$ اُم را آتش می‌زنند و این آتش از هر دو طرف با سرعتی برابر شروع به پیشروی می‌کند و تا وقتی که به یک آلارم نرسد، متوقف نمی‌شود؛ پس از رسیدن آتش به هر خانه، تعداد خیارهای آن نصف می‌شود (مقدار جزء صحیح آن مورد نظر است). توجه کنید هنگامی که یک طرف آتش به یک آلارم برسد بلافاصله آتش از هر دو طرف خاموش می‌شود (دقت کنید خانه‌ای که در آن آلارم است آتش نمی‌گیرد). بعد از پایان آتش سوزی ابواسحاق یک آلارم در خانهٔ $x$ قرار می‌دهد. کل فرآیند پیشروی آتش در یک روز انجام می‌شود و به روزهای بعدی کشیده نمی‌شود.
در ابتدا فقط در خانه‌های $0$ و $ n + 1 $ یک آلارم وجود دارد (یکی قبل از خانه اول مزرعه و یکی بعد از خانه آخر آن) و بقیه خانه‌ها بدون آلارم هستند. برای هر اتفاق از نوع یک، مجموع تعداد خیارها را خروجی دهید.
ورودی
در خط اول دو عدد $n$ و $q$ می‌آید که به ترتیب تعداد خانه‌های مزرعه ابواسحاق و تعداد روز‌هایی است که مزرعه فعالیت می‌کند.
در خط دوم $n$ عدد می‌آید که عدد $i$ اُم، برابر با $a_i$ است.
در خط سوم نیز $n$ عدد می‌آید که عدد $i$ اُم، برابر با $b_i$ یا همان نرخ رشد خانهٔ $i$ ام است.
سپس در هر خط از $q$ خط بعدی ابتدا $t$ یا همان نوع اتفاق آمده که یکی از دو حالت زیر را دارد:
- اگر $t = 1$ باشد آنگاه اتفاق از نوع اول است و در ادامه همان خط دو عدد $l$ و $r$ ورودی داده می‌شود.
- اگر $t = 2$ باشد آنگاه اتفاق از نوع دوم است و در ادامه همان خط عدد $x$ ورودی داده می‌شود.
تضمین می‌شود مقدار $x$ برای هرکدام از $q$ روز متفاوت است. $$ 1 \le n \le 100\ 000 $$ $$ 1 \le q \le 300\ 000 $$ $$ 1 \le l, r, x \le n $$ $$ 1 \le a_i, b_i \le 1\ 000\ 000 $$
خروجی
به ازای هر اتفاق نوع اول مقدار خواسته شده را در یک سطر خروجی دهید.
مثال
ورودی نمونه ۱
7 4
10 10 10 10 10 10 10
1 3 4 2 3 2 4
2 2
1 1 4
2 4
1 3 7
خروجی نمونه ۱
40
77
خیارهای اولیه مزرعه به صورت $[10 ,10 ,10 ,10 ,10 ,10 ,10]$ است.
در ابتدای روز اول خیارها رشد کرده و مزرعه به صورت $[11, 13, 14, 12, 13, 12, 14]$ درمیآید، در انتهای روز اول خانه دوم آتش گرفته در نتیجه آتش پیشروی کرده تا به یک آلارم برسد(در این روز آتش قبل از آلارم خانه $0$ ام متوقف می‌شود) در نتیجه مقدار خیارها در خانه‌های $1,2,3$ نصف می‌شود و مزرعه در انتهای روز به صورت $[5, 6, 7, 12, 13, 12, 14]$ درمیآید.
در ابتدای روز دوم با رشد خیارها مزرعه به صورت $[6, 9, 11, 14, 16, 14, 18]$ درمیآید. سپس جمع تعداد خیارهای خانه‌های $1,2,3,4$ را خروجی می‌دهیم.
در روز سوم مانند روزهای قبل پس از رشد داریم $[7, 12, 15, 16, 19, 16, 22]$ و با آتش گرفتن خانه چهارم و پیشروی آن تا رسیدن به اولین آلارم از یک سمت، تعداد خیارهای خانه‌های $3,4,5$ نصف خواهد شد و مزرعه به صورت $[7, 12, 7, 8, 9, 16, 22]$ درمیآید. روز چهارم نیز به همین ترتیب سپری خواهد شد.
ارسال پاسخ برای این سؤال