+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- جمشید از جایگشت‌ها بدش می‌آید و یک جایگشت به طول $n$ دارد که می‌خواهد طی تعدادی مرحله آن را پاک کند. جمشید در هر مرحله می‌تواند یکی از اعداد جایگشت مانند $p_i$ که هنوز پاک نشده را انتخاب و خود آن عدد و تمام اعداد کوچکتر سمت راست و یا تمام اعداد کوچکتر سمت چپ آن عدد را پاک کند. با انجام این کار جمشید به میزان $b_i$ خسته می‌شود. دقت کنید که اعدادی که پاک نشده‌اند به یکدیگر می‌چسبند. برای مثال اگر در جایگشت $p = \langle 1, 3, 4, 2, 5 \rangle$ با دنباله $b = \langle 1, 2, 3, 4, 5 \rangle$ عدد $p_2 = 3$ را انتخاب کنیم و تمام اعداد کوچکتر سمت راست آن را پاک کنیم، به جایگشت $p = \langle 1, 4, 5 \rangle$ با دنباله $b = \langle 1, 3, 5 \rangle$ می‌رسیم. جمشید می‌خواهد پس از پاک کردن جایگشت فوتبال بازی کند پس می‌خواهد با کمترین میزان خستگی ممکن کل جایگشت را پاک کند. مقدارهای $b_i$ در جایگشت جمشید $q$ بار تغییر می‌کنند و در هر بار تغییر یکی از مقادیر $b_i$ عوض می‌شود. به جمشید کمک کنید تا کمترین میزان خستگی ممکن برای حذف کل جایگشت قبل از تمام تغییرات و پس از هر تغییر را محاسبه کند. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $q$ به‌ترتیب می‌آیند. $$1 \leq n \leq 3 \times 10^5$$ $$0 \leq q \leq 3 \times 10^5$$ در خط دوم ورودی $n$ عدد می‌آید که به ترتیب مقادیر $p_i$ را مشخص می‌کنند. در خط سوم ورودی $n$ عدد می‌آید که به ترتیب مقادیر اولیه $b_i$ را مشخص می‌کنند. در $q$ خط بعدی در هر خط دو عدد $x_i$ و ‌ $y_i$ می آیند که تغییر $i$ ام را نشان می‌دهند و باید تغییر $b_{x_i} = y_i$ باید صورت بگیرد. $$1 \leq p_i , x_i \leq n$$ $$1 \leq b_i , y_i \leq 10^9$$ # خروجی در $q+1$ خط ، در خط اول کمترین میزان خستگی جمشید برای پاک کردن جایگشت قبل از اعمال تغییرات و به ترتیب در خط $i+1$ ام ، کمترین میزان خستگی جمشید برای پاک کردن جایگشت پس از اعمال $i$ تغییر اول را خروجی دهید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۵ | $b_i=1$ و $q=0$ | | ۲ | ۱۰ | $q=0$ و $n=20$ | | ۳ | ۲۵ | $q=0$ | | ۴ | ۲۵ | $1 \le b_i \le 10$ و $1 \le y_i \le 10$ | | ۵ | ۳۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 1 1 2 4 3 2 5 3 4 2 3 ``` ## خروجی نمونه ۱ ``` 7 6 ``` در این مثال قبل از تغییرات کافی است عدد $3$ و اعداد کوچکتر سمت چپ آن را پاک کنیم و به مقدار $4$ واحد خسته می‌شویم و سپس تنها عدد باقی‌مانده عدد $4$ است که آن را حذف می‌کنیم و به مقدار $3$ خسته می‌شویم که در کل $7$ واحد خسته می‌شویم. پس از تغییر $b_2 = 3$ ابتدا عدد $2$ و اعداد کوچکتر چپ آن را حذف می‌کنیم و سپس عدد $4$ و اعداد کوچکتر سمت راست آن که در انتها کل جایگشت حذف می‌شود و میزان کل خستگی $6$ خواهد بود. ## ورودی نمونه ۲ ``` 5 2 4 5 1 3 2 6 8 1 3 2 1 3 4 1 ``` ## خروجی نمونه ۲ ``` 12 11 10 ```

حل سؤال در بانک سؤالات