+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- بعد از دیدن فیلم ماداگاسکار، علی‌جان عاشق شخصیت گورخر شد و تحقیقات خودش را روی این گونه از جانوران آغاز کرد. او جدیدا متوجه شده در یکی از پارک‌های ملی، گورخری وجود دارد که رنگ بدن او بسیار جالب است. علی‌جان بدن گورخر را به یک گراف بدون‌جهت و همبند شبیه‌سازی کرد که هر راس آن سیاه یا سفید است. گورخر این قابلیت را دارد که یکی از رئوسش مانند $v$ را انتخاب کنیم و رنگ تمام رئوس مولفه همبندی همرنگ با $v$ عوض شود. به بیانی دیگر، رنگ راس $u$ عوض می‌شود اگر مسیری از $v$ به $u$ وجود داشته باشد که تمام رئوس آن همرنگ هستند. علی‌جان عاشق گورخرها است و دوست ندارد که تمام رئوس مربوط به بدن گورخر همرنگ شود. برای اینکه بتواند از گورخر محافظت کند، نیاز دارد تا کمترین عملیات ممکن برای همرنگ شدن تمامی رئوس را پیدا کند. به او در پیدا کردن این مقدار کمک کنید. برای درک بهتر سوال، به توضیحات نمونه‌های ورودی توجه کنید. # ورودی در خط اول ورودی دو عدد طبیعی $n$ تعداد رئوس و $m$ عداد یال‌ها به‌ترتیب می‌آیند. $$1 \leq n \leq 2000$$ $$1 \leq m \leq 5000$$ در خط دوم ورودی $c_1, c_2, \cdots c_n$ به‌ترتیب می‌آیند. $c_i$ مربوط به رنگ راس $i$ ام می‌باشد. مقدار $0$ بیانگر رنگ سفید و مقدار $1$ بیانگر راس سیاه است. $$0 \leq c_i \leq 1$$ در هر یک از $m$ خط بعدی، دو سر هر یال $v_i$ و $u_i$ می‌آید. $$1 \leq v_i, u_i \leq n$$ # خروجی در تنها خط خروجی، کمترین عملیات ممکن برای اینکه گورخر تک‌رنگ شود را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۱۰ | $n \le 20$ | | ۲ | ۱۰ | $m = n-1$ و به ازای هر $1 \leq i \leq n - 1$ یک یال بین رئوس $i$ و $i+1$ وجود دارد. | | ۳ | ۴۰ | $m = n-1$ | | ۴ | ۴۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 8 1 0 0 1 1 0 1 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 ``` ## خروجی نمونه ۱ ``` 2 ``` علی‌جان می‌تواند در دو مرحله با انتخاب رئوس ۴ و ۱ همه رئوس گراف را سفید کند. ## ورودی نمونه ۲ ``` 9 8 1 0 1 0 1 0 1 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 ``` ## خروجی نمونه ۲ ``` 4 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- اگر $p = \langle p_1, p_2, \cdots, p_{3n} \rangle$ جایگشتی از اعداد $1$ تا $3n$ باشد، سیانه‌ی آن را دنباله‌ی $q = \langle q_1, q_2, \cdots, q_n \rangle$ تعریف می‌کنیم که $q_i$ در این دنباله برابر با میانه‌ی $\langle p_{3i - 2}, p_{3i - 1}, p_{3i} \rangle$ می‌باشد. برای مثال سیانه‌ی دنباله‌ی $p = \langle 4, 8, 9, 7, 1, 3, 2, 6, 5 \rangle$ برابر با $q = \langle 8, 3, 5 \rangle$ است. باقی‌مانده‌ی تعداد سیانه‌های متفاوت بین تمام جایگشت‌های اعداد $1$ تا $3n$ بر $10^9+7$ را پیدا کنید. # ورودی در خط اول ورودی عدد طبیعی $n$ می‌آید. $$1 \le n \le 10^6$$ # خروجی در تنها خط خروجی باقی‌مانده تقسیم تعداد سیانه‌های متفاوت را بر $10^9+7$ خروجی دهید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:------------------:|:----------:|:------------------:| | ۱ | ۴ | $n \le 4$ | | ۲ | ۱۶ | $n \le 300$ | | ۳ | ۳۱ | $n \le 3000$ | | ۴ | ۴۹ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 2 ``` ## خروجی نمونه ۲ ``` 8 ``` در این نمونه، سیانه‌هایی که ساخته می شود این دنباله‌ها می‌باشد: $\langle 2, 4 \rangle$, $\langle 2, 5 \rangle$, $\langle 3, 4 \rangle$, $\langle 3, 5 \rangle$, $\langle 4, 2 \rangle$, $\langle 5, 2 \rangle$, $\langle 4, 3 \rangle$, $\langle 5, 3 \rangle$ ## ورودی نمونه ۳ ``` 7 ``` ## خروجی نمونه ۳ ``` 141629040 ```

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی اول فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- جمشید از جایگشت‌ها بدش می‌آید و یک جایگشت به طول $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 ```