- محدودیت زمان: ۲.۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک بازی مدیریت شهری، باید ۳ ساختمان را به شکلی مدیریت کنید که مصرف برق آن‌ها به بهینه‌ترین حالت ممکن برسد. برای فهمیدن این موضوع، داور بازی در هر مرحله $m$ کار انجام می‌دهد تا تعداد امتیازهای منفی را محاسبه کند. این کارها یکی از دو نوع زیر می‌باشند:
- داور مصرف برق واحد $k$ام از ساختمان $a$ را به $x$ تغییر می‌دهد. به بیانی $a_k = x$.
- داور با دادن مقدار $r$ به دنبال سه واحد $i$ و $j$ و $k$ از سه ساختمان $a$ و $b$ و $c$ می‌گردد که شرایط زیر را داشته باشند و به ازای هر بار یافتن این الگو یک امتیاز به بازیکن می‌دهد: $$1≤i<j<k≤r$$ $$b_{a_i} = a_j = c_{a_k}$$
- منظور از $a_i$ مصرف برق واحد $i$ام از ساختمان $a$ می‌باشد.
ورودی
در خط اول ورودی عدد $n$ به عنوان تعداد واحدهای سه ساختمان و $m$ به عنوان تعداد کارهایی که داور انجام می‌دهد داده می‌شوند. $$ 1 \leq n \leq 200\ 000 $$ $$ 1 \leq m \leq 500\ 000 $$
در ادامه در سه خط سه دنباله به طول $n$ به ترتیب به عنوان مصرف برق واحدهای ساختمان $a$ و $b$ و $c$ داده می‌شود.
$$ 1 \leq a_i, b_i, c_i \leq n $$
در ادامه در $m$ خط کارهای داور می‌آیند که به قالب زیر هستند:
CHANGE(k,x) := عنصر $k$ام در دنبالۀ اول به $x$ تغییر می‌کند
PRINT(r) := کار نوع دوم است که در جوابش یک عدد (امتیازهایی که به بازیکن می‌دهد) باید بدهید
$$ 1 \leq k, x, r \leq n $$
خروجی
به ازای هر پرسش نوع دوم، مقدار عددی خروجی را چاپ کنید.
مثال
ورودی نمونه ۱
5 4
1 2 3 4 5
2 3 4 5 1
5 1 2 3 4
PRINT(5)
CHANGE(2,3)
PRINT(4)
PRINT(5)
خروجی نمونه ۱
3
0
2
ارسال پاسخ برای این سؤال