- محدودیت زمان: ۳ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
بدخواه، بدِ جامعه‌ی هنری را هم میخواهد. او تدارک ساخت فیلمی را داده و از $n$ بازیگر مطرح سینما دعوت کرده که در فیلم او بازی کنند. آن‌ها با دیدن فیلمنامه قبول کردند، غافل از نقشه‌هایی که بدخواه برایشان دارد...
بدخواه در همان روز اول کار، به سراغ فیلمبرداری صحنه‌ی پایانی میرود - صحنه‌ی دوئل. در این صحنه، این $n$ بازیگر حضور دارند و هریک کسی را در ذهن خود هدف میگیرد، بطوری که هرکس توسط دقیقاً یک نفر هدف‌گرفته شود. بازیگر $i$ـم، بازیگر $p_i$ـم را هدف قرار می‌دهد. در یک لحظه همه‌ی بازیگرها اقدام به شلیک میکنند اما سرعت عکس‌العمل آن‌ها برابر نیست و بازیگر $i$ـم، $t_i$ میلی ثانیه طول میکشد تا ماشه را بچکاند و طعم مرگ را به بازیگر $p_i$ـم بچشاند. بدلیل حرفه‌ای بودن این بازیگرها، هریک دقیقاً به اندازه‌ی مقدار تعیین شده ($t_i$ میلی ثانیه) صبر کرده و سپس بسرعت، هفت‌تیر را بالا آورده و به هدفش ($p_i$ـمین بازیگر) شلیک میکند. این اعمال در زمان اندک انجام میشود.(می‌توان فرض کرد اگر شلیک انجام شود، فرد $p_i$ در لحظه‌ی $t_i$ می‌میرد.)
اما بدخواهِ نابکار، در هفت‌تیر این افتخارات ملی، تیر‌های واقعی گمارده و با هر شلیک، یک جوان هنرمند می‌میرد. اگر بازیگر $i$ـم قبل از زمان $t_i$ مرده باشد، در لحظه‌ی $t_i$ شلیکی از طرف این بازیگر صورت نمی‌گیرد.
حال بدخواه سناریو را به شما می‌دهد (مقدار $t_i$ها و $p_i$ها) و از شما می‌پرسد که با اجرای این سناریو، در نهایت چند بازیگر زنده می‌مانند. سپس به امید کشته‌های بیشتر، $q$ بار این سناریو را عوض میکند؛ هربار یکی از $t_i$ها را تغییر می‌دهد و پس از هر تغییر نیز از شما می‌پرسد که حال چطور؟! و شما باید تعداد بازیگرهای زنده پس از اجرای این سناریو را به او بگویید.
دقت کنید که تغییرات انجام شده باقی می‌مانند؛ بعنوان مثال دومین تغییر روی سناریو ای صورت میگیرد که پیش از آن، اولین تغییر روی آن اعمال شده است.
ورودی
سطر اول ورودی شامل یک عدد $n$ است که نمایانگر تعداد بازیگرها در سناریوی بدخواه است.
در سطر دوم ورودی، $n$ عدد متفاوت آمده است. $i$ـمین عدد $p_i$ است که نمایانگر هدف بازیگر $i$ـم در سناریوی اولیه است.
در سطر سوم ورودی، $n$ عدد آمده است. $i$ـمین عدد $t_i$ است که نمایانگر زمان عکس‌العمل بازیگر $i$ـم در سناریوی اولیه است.
در سطر چهارم ورودی، یک عدد $q$ آمده است که نمایانگر تعداد تغییرهای سناریو است. سپس در $i$ـمین سطر از $q$ سطر بعدی، دو عدد $b_i$ و $y_i$ آمده است که یعنی در تغییر $i$ـم، زمان عکس‌العمل بازیگر $b_i$ـم در سناریو به $y_i$ تغییر میکند.
تضمین میشود که همه‌ی اعداد $t_1, t_2, t_3, ..., t_n, y_1, y_2, y_3, ..., y_q$ متفاوت هستند.
$$ p_i \neq i $$$$2 \le n \le 200\ 000$$ $$0 \le q \le 200\ 000$$ $$1 \le p_i, b_i \le n$$ $$1 \le y_i, t_i \le 1\ 000\ 000\ 000$$
خروجی
خروجی باید شامل $q + 1$ سطر باشد که هرکدام شامل یک عدد هستند. عدد در سطر اول باید برابر تعداد بازیگرهای زنده درصورت اجرای سناریوی اولیه است. عدد در $i + 1$ـمین سطر باید برابر تعداد بازیگرهای زنده باشد، در صورتی که $i$ تغییر اول روی سناریوی اولیه انجام شود و سناریو را اجرا کنند.
مثال
ورودی نمونه
4
2 3 4 1
1 3 4 5
3
1 8
2 7
3 6
خروجی نمونه
2
2
1
1
ارسال پاسخ برای این سؤال