+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- پس از اینکه روابط ایران و مصر بهبود یافت، سه نفر از ایرانیان توانستند ویزای مصر را اخذ کنند. آن‌ها پس از رسیدن به مصر، قصد دارند که اول از خیابان معروف «طلعت حرب» دیدن کنند. در این خیابان $n$ ساختمان وجود دارد که در یک خط صاف قرار دارند و به ترتیب از چپ به راست از $1$ تا $n$ شماره‌گذاری شده‌اند. همجنین زیبایی ساختمان $i$م برابر $a_i$ است. حال در فرودگاه $Q$ تاکسی موجود است. تاکسی شماره $i$ آن سه نفر را در فرودگاه سوار کرده و مقابل ساختمان $l_i$ پیاده می‌کند و سپس در مقابل ساختمان $r_i$ منتظر می‌ماند تا آن‌ها را سوار کرده و به سمت هتل ببرد. $(l_i≤r_i)$ آن‌ها اگر تاکسی شماره $i$ را انتخاب کنند، پس از پیاده شدن از تاکسی همواره به سمت راست می‌روند تا به ساختمان $r_i$ برسند و آن‌جا سوار تاکسی شوند. آن‌ها قصد دارند از تعدادی (حداقل یک) ساختمان بازدید کنند به طوری که ساختمان‌های بازدید شده **متوالی** باشند. توجه کنید در حالت عادی فقط از مقابل ساختمان رد می‌شوند و لزوماً از هر ساختمانی که از رو به روی آن گذر می‌کنند بازدید نمی‌کنند. - نفر اول در صورتی از دیدن یک ساختمان راضی است که زیبایی آن از تمام ساختمان‌های قبلی **بازدید شده** اکیداً بیشتر باشد. - نفر دوم نیز در صورتی از دیدن یک ساختمان راضی است که زیبایی آن ساختمان از تمام ساختمان‌هایی که در ادامه از آن‌ها **بازدید می‌کنند**، اکیداً کمتر باشد. - نفر سوم نیز چون از دو نفر دیگر پیرتر است، سلیقه‌ی عجیبی ندارد و از دیدن تمامی ساختمان‌ها راضی است. بازدید از یک ساختمان در صورتی برای آن‌ها خوشایند است که اکثریت آن‌ها (حداقل دو نفر) راضی به بازدید از آن ساختمان باشند. آن‌ها به ازای هر کدام از تاکسی‌ها می‌خواهند بدانند که به چند طریق می‌توانند تعدادی از ساختمان‌هایی که از رو به روی آن‌ها گذر می‌کنند را انتخاب کنند و از آن‌ها بازدید کنند. توجه کنید که آن‌ها از ساختمان های $l_i$ و $r_i$ نیز می‌توانند بازدید کنند. به عبارت دیگر آن‌ها از ساختمان‌های یک زیربازه از بازه‌ی $[l_i,r_i]$ بازدید می‌کنند. همچنین نفر سوم به عنوان پیرترین نفر جمع به شما توصیه می‌کند که برای فهم بهتر سوال به نمونه ورودی ها توجه کنید. # ورودی در خط اول ورودی، $n$ یا همان تعداد ساختمان ها می‌آید. $$1 \leq n \leq 500 \, 000$$ در خط دوم ورودی، $n$ عدد صحیح می آیند که عدد $i$ ام همان $a_i$ است. $$0 \leq a_i \leq 10^ 9$$ در خط سوم ورودی، $Q$ یا همان تعداد تاکسی ها می‌آید. $$1 \leq Q \leq 500 \, 000$$ در $Q$ خط بعدی در هر خط دو عدد $r_i$ و $l_i$ به ترتیب می‌آیند. $$1 \leq l_i \leq r_i \leq n$$ # خروجی در تنها خط خروجی $Q$ عدد چاپ کنید که عدد $i$ ام تعداد حالت‌های بازدید کردن آن‌ها در صورت استفاده از تاکسی $i$ام است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-----:|:-------:|:----------------------------:| | ۱ | ۹ | $n \leq 500$ | | ۲ | ۱۶ | $ n \leq 5000$ | | ۳ | ۳۶ | $n \leq 10^5, Q \leq 3000$ | | ۴ | ۳۹ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 5 5 4 1 3 2 5 1 5 2 5 2 4 1 3 1 2 ``` ## خروجی نمونه ۱ ``` 11 9 6 5 3 ``` ## ورودی نمونه ۲ ``` 9 5 2 3 3 6 4 6 4 1 5 1 9 4 9 3 8 2 5 7 8 ``` ## خروجی نمونه ۲ ``` 29 15 18 10 3 ``` در ورودی نمونه اول به ازای تاکسی دوم، تعداد کل حالت‌هایی که می‌توانند از تعدادی ساختمان متوالی بازدید بکنند برابر $10$ است. از بین این $10$ حالت، حالتی که از کل ساختمان‌های بازه $[2, 5]$ بازدید بکنند خوشایند نیست؛ زیرا نفر اول و دوم راضی به بازدید از ساختمان با زیبایی $3$ نیستند.

بریم مصر

محدودیت زمان: ۳ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت
آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

پس از اینکه روابط ایران و مصر بهبود یافت، سه نفر از ایرانیان توانستند ویزای مصر را اخذ کنند. آن‌ها پس از رسیدن به مصر، قصد دارند که اول از خیابان معروف «طلعت حرب» دیدن کنند. در این خیابان $n$ ساختمان وجود دارد که در یک خط صاف قرار دارند و به ترتیب از چپ به راست از $1$ تا $n$ شماره‌گذاری شده‌اند. همجنین زیبایی ساختمان $i$ م برابر $a_i$ است.

حال در فرودگاه $Q$ تاکسی موجود است. تاکسی شماره $i$ آن سه نفر را در فرودگاه سوار کرده و مقابل ساختمان $l_i$ پیاده می‌کند و سپس در مقابل ساختمان $r_i$ منتظر می‌ماند تا آن‌ها را سوار کرده و به سمت هتل ببرد. $(l_i≤r_i)$ آن‌ها اگر تاکسی شماره $i$ را انتخاب کنند، پس از پیاده شدن از تاکسی همواره به سمت راست می‌روند تا به ساختمان $r_i$ برسند و آن‌جا سوار تاکسی شوند.

آن‌ها قصد دارند از تعدادی (حداقل یک) ساختمان بازدید کنند به طوری که ساختمان‌های بازدید شده متوالی باشند. توجه کنید در حالت عادی فقط از مقابل ساختمان رد می‌شوند و لزوماً از هر ساختمانی که از رو به روی آن گذر می‌کنند بازدید نمی‌کنند.

نفر اول در صورتی از دیدن یک ساختمان راضی است که زیبایی آن از تمام ساختمان‌های قبلی بازدید شده اکیداً بیشتر باشد.
نفر دوم نیز در صورتی از دیدن یک ساختمان راضی است که زیبایی آن ساختمان از تمام ساختمان‌هایی که در ادامه از آن‌ها بازدید می‌کنند، اکیداً کمتر باشد.
نفر سوم نیز چون از دو نفر دیگر پیرتر است، سلیقه‌ی عجیبی ندارد و از دیدن تمامی ساختمان‌ها راضی است.

بازدید از یک ساختمان در صورتی برای آن‌ها خوشایند است که اکثریت آن‌ها (حداقل دو نفر) راضی به بازدید از آن ساختمان باشند.

آن‌ها به ازای هر کدام از تاکسی‌ها می‌خواهند بدانند که به چند طریق می‌توانند تعدادی از ساختمان‌هایی که از رو به روی آن‌ها گذر می‌کنند را انتخاب کنند و از آن‌ها بازدید کنند. توجه کنید که آن‌ها از ساختمان های $l_i$ و $r_i$ نیز می‌توانند بازدید کنند. به عبارت دیگر آن‌ها از ساختمان‌های یک زیربازه از بازه‌ی $[l_i,r_i]$ بازدید می‌کنند.

همچنین نفر سوم به عنوان پیرترین نفر جمع به شما توصیه می‌کند که برای فهم بهتر سوال به نمونه ورودی ها توجه کنید.

ورودی🔗

در خط اول ورودی، $n$ یا همان تعداد ساختمان ها می‌آید. $1 \leq n \leq 500 \, 000$

در خط دوم ورودی، $n$ عدد صحیح می آیند که عدد $i$ ام همان $a_i$ است. $0 \leq a_i \leq 10^ 9$

در خط سوم ورودی، $Q$ یا همان تعداد تاکسی ها می‌آید. $1 \leq Q \leq 500 \, 000$

در $Q$ خط بعدی در هر خط دو عدد $r_i$ و $l_i$ به ترتیب می‌آیند. $1 \leq l_i \leq r_i \leq n$

خروجی🔗

در تنها خط خروجی $Q$ عدد چاپ کنید که عدد $i$ ام تعداد حالت‌های بازدید کردن آن‌ها در صورت استفاده از تاکسی $i$ ام است.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۹	$n \leq 500$
۲	۱۶	$n \leq 5000$
۳	۳۶	$n \leq 10^5, Q \leq 3000$
۴	۳۹	بدون محدودیت اضافی

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

11 9 6 5 3

ورودی نمونه ۲🔗

9
5 2 3 3 6 4 6 4 1
5
1 9
4 9
3 8
2 5
7 8

خروجی نمونه ۲🔗

29 15 18 10 3

در ورودی نمونه اول به ازای تاکسی دوم، تعداد کل حالت‌هایی که می‌توانند از تعدادی ساختمان متوالی بازدید بکنند برابر $10$ است. از بین این $10$ حالت، حالتی که از کل ساختمان‌های بازه $[2, 5]$ بازدید بکنند خوشایند نیست؛ زیرا نفر اول و دوم راضی به بازدید از ساختمان با زیبایی $3$ نیستند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- **امتیاز** یک دنباله برابر تعداد جفت خانه‌های مجاوری است که مجموع آن‌ها برابر $k$ می‌شود. به عنوان مثال اگر $k=3$ باشد، امتیاز دنباله $⟨1,2,3,0,2⟩$ برابر $2$ است. به شما عدد صحیح نامنفی $k$ و یک دنباله $n$ تایی از اعداد داده می‌شود. شما باید تعداد جایگشت‌های از این دنباله که امتیازشان برابر $i$ می‌شود را به ازای هر $i$ از $0$ تا $n - 1$ بدست آورید. چون اعداد جواب ممکن است بزرگ شود کافی است که باقی‌مانده تقسیم هر عدد را بر $998244353$ چاپ کنید. توجه کنید که اعداد مساوی قابل تمایز هستند. # ورودی در خط اول ورودی، دو عدد صحیح $n$ و $k$ به ترتیب می آیند. $$1 \leq n \leq 5000, \quad 0 \leq k \leq 10^9$$ در خط دوم ورودی، $n$ عدد صحیح می آیند که نشان دهنده دنباله ورودی است (اعداد دنباله نامنفی و کمتر از $10^9$ هستند). # خروجی در تنها خط خروجی $n$ عدد چاپ کنید که به ترتیب برابر با تعداد جایگشت‌های دنباله با امتیاز $0, 1, \cdots , n - 1$ باقی‌مانده بر $998244353$ است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-----:|:-------:|:----------------------------:| | ۱ | ۴ | $n \leq 10$ | | ۳ | ۱۲ | تعداد اعداد متمایز حداکثر دو است. | | ۴ | ۱۷ | تعداد اعداد متمایز حداکثر سه است. | | ۵ | ۲۳ | $n \leq 500$ | | ۶ | ۴۴ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 5 3 1 2 1 2 1 ``` ## خروجی نمونه ۱ ``` 0 24 36 48 12 ```

مجاور خوب

محدودیت زمان: ۱ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت
آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

امتیاز یک دنباله برابر تعداد جفت خانه‌های مجاوری است که مجموع آن‌ها برابر $k$ می‌شود. به عنوان مثال اگر $k=3$ باشد، امتیاز دنباله $⟨1,2,3,0,2⟩$ برابر $2$ است.

به شما عدد صحیح نامنفی $k$ و یک دنباله $n$ تایی از اعداد داده می‌شود. شما باید تعداد جایگشت‌های از این دنباله که امتیازشان برابر $i$ می‌شود را به ازای هر $i$ از $0$ تا $n - 1$ بدست آورید. چون اعداد جواب ممکن است بزرگ شود کافی است که باقی‌مانده تقسیم هر عدد را بر $998244353$ چاپ کنید.

توجه کنید که اعداد مساوی قابل تمایز هستند.

ورودی🔗

در خط اول ورودی، دو عدد صحیح $n$ و $k$ به ترتیب می آیند. $1 \leq n \leq 5000, \quad 0 \leq k \leq 10^9$

در خط دوم ورودی، $n$ عدد صحیح می آیند که نشان دهنده دنباله ورودی است (اعداد دنباله نامنفی و کمتر از $10^9$ هستند).

خروجی🔗

در تنها خط خروجی $n$ عدد چاپ کنید که به ترتیب برابر با تعداد جایگشت‌های دنباله با امتیاز $0, 1, \cdots , n - 1$ باقی‌مانده بر $998244353$ است.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۴	$n \leq 10$
۳	۱۲	تعداد اعداد متمایز حداکثر دو است.
۴	۱۷	تعداد اعداد متمایز حداکثر سه است.
۵	۲۳	$n \leq 500$
۶	۴۴	بدون محدودیت اضافی

مثال‌ها🔗

ورودی نمونه ۱🔗

5 3
1 2 1 2 1

خروجی نمونه ۱🔗

0 24 36 48 12

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت + آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران ---------- یاسین تصمیم گرفته شجره‌نامه‌ی خانواده خود را بسازد. او تصویر $n + 1$ نفر را در اختیار دارد. همچنین سن هر کدام از افراد را می‌داند. اما از بین این افراد فقط بزرگ خاندان را می‌شناسد. یاسین نزد بزرگ خاندان می‌رود تا از او برای ساخت شجره‌نامه کمک بگیرد. اما بزرگ خاندان به او می‌گوید این مسخره‌بازیا چیه بچه و برای او یک سوال مطرح می‌کند تا توانایی درخت ساختنش را به چالش بکشد. بزرگ خاندان به یاسین می‌گوید که برایش یک درخت ریشه‌دار بسازد. هر راس این درخت یک اندیس دارد و روی راس با اندیس $i$، عدد $a_i$ نوشته شده است. در ابتدا درخت یک راس با اندیس $0$ دارد که روی آن عدد $+\infty$ نوشته شده است. بزرگ خاندان در $n$ مرحله، هر مرحله یک راس به درخت اضافه می‌کند. او در مرحله‌ی $i$-ام عدد $p_i$ را به یاسین می‌گوید و سپس از او می‌خواهد راس $i$ را به یکی از دو نحو زیر به درخت اضافه کند: 1. راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد. ($0 \leq p_i < i$) 2. بزرگترین خاندان ابتدا از یاسین می‌خواهد که پایین ترین جد راس $p_i$ را پیدا کند که عددش از $a_i$ کمتر نباشد. ($0 \leq p_i < i$) در صورتی که $ a_{p_i} \geq a_i$ ، راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد. در غیر این صورت یاسین باید رئوس $v$ و $u$ را طوری پیدا کند که : - هر دو جد راس $p_i$ باشند. (راس $p_i$ هم یکی از اجداد خودش است.) - راس $v$ پدر راس $u$ باشد. - نامساوی $a_u < a_i \leq a_v$ و به ازای هر راس مانند $z$ که $v$ جد $z$ و $z$ جد $p_i$ باشد داریم $a_z < a_i$ - حال راس $i$ را وسط یال $v$ و $u$ اضافه می‌کنیم. یعنی راس $v$ پدر راس $i$ و راس $i$ پدر راس $u$ می‌شود. در انتها بزرگ خاندان از او می‌خواهد به ازای هر راس از $1$ تا $n$ پدرش در درخت نهایی را به او بگوید. یاسین که از برآورده کردن خواسته‌های پیرمرد‌ها و درخت‌هایشان خسته شده بود از شما می‌خواهد کمکش کنید تا خود را به بزرگ خاندان ثابت کند. # ورودی در خط اول ورودی $n$ می آید. $$1 \leq n \leq 10^6$$ سپس در خط $i$ام از $n$ خط بعدی، سه عدد $t_i$، $p_i$ و $a_i$ به ترتیب آمده اند. $$t_i \in \{1, 2\} ,\quad 0 \leq p_i < i, \quad 1 \leq a_i \leq n$$ اگر $t_i$ برابر با $1$ بود این عملیات از نوع اول و اگر برابر با $2$ بود از نوع دوم است. # خروجی در تنها خط خروجی باید $n$ عدد چاپ کنید که عدد $i$ ام باید پدر راس $i$ در درخت نهایی باشد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-----:|:-------:|:----------------------------:| | ۱ | ۷ | $n \leq 5000$ | | ۲ | ۱۲ | $a_i \leq 2$ | | ۳ | ۸۱ | بدون محدودیت اضافی | # مثال‌ها ## ورودی نمونه ۱ ``` 6 2 0 1 1 1 3 2 2 6 2 1 1 2 4 4 2 3 3 ``` ## خروجی نمونه ۱ ``` 5 1 0 1 3 3 ```

شجره‌نامه

محدودیت زمان: ۳ ثانیه
محدودیت حافظه: ۵۱۲ مگابایت
آزمون عملی سوم فاینال سی و سومین دوره المپیاد کامپیوتر ایران

یاسین تصمیم گرفته شجره‌نامه‌ی خانواده خود را بسازد.

او تصویر $n + 1$ نفر را در اختیار دارد. همچنین سن هر کدام از افراد را می‌داند. اما از بین این افراد فقط بزرگ خاندان را می‌شناسد.

یاسین نزد بزرگ خاندان می‌رود تا از او برای ساخت شجره‌نامه کمک بگیرد. اما بزرگ خاندان به او می‌گوید این مسخره‌بازیا چیه بچه و برای او یک سوال مطرح می‌کند تا توانایی درخت ساختنش را به چالش بکشد.

بزرگ خاندان به یاسین می‌گوید که برایش یک درخت ریشه‌دار بسازد. هر راس این درخت یک اندیس دارد و روی راس با اندیس $i$ ، عدد $a_i$ نوشته شده است. در ابتدا درخت یک راس با اندیس $0$ دارد که روی آن عدد $+\infty$ نوشته شده است.

بزرگ خاندان در $n$ مرحله، هر مرحله یک راس به درخت اضافه می‌کند.

او در مرحله‌ی $i$ -ام عدد $p_i$ را به یاسین می‌گوید و سپس از او می‌خواهد راس $i$ را به یکی از دو نحو زیر به درخت اضافه کند:

راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد. ( $0 \leq p_i < i$ )
بزرگترین خاندان ابتدا از یاسین می‌خواهد که پایین ترین جد راس $p_i$ را پیدا کند که عددش از $a_i$ کمتر نباشد. ( $0 \leq p_i < i$ ) در صورتی که $a_{p_i} \geq a_i$ ، راس $i$ را فرزند راس $p_i$ قرار می‌دهد؛ یعنی یک یال بین راس $i$ و $p_i$ می‌کشد. در غیر این صورت یاسین باید رئوس $v$ و $u$ را طوری پیدا کند که :
- هر دو جد راس $p_i$ باشند. (راس $p_i$ هم یکی از اجداد خودش است.)
- راس $v$ پدر راس $u$ باشد.
- نامساوی $a_u < a_i \leq a_v$ و به ازای هر راس مانند $z$ که $v$ جد $z$ و $z$ جد $p_i$ باشد داریم $a_z < a_i$
- حال راس $i$ را وسط یال $v$ و $u$ اضافه می‌کنیم. یعنی راس $v$ پدر راس $i$ و راس $i$ پدر راس $u$ می‌شود.

در انتها بزرگ خاندان از او می‌خواهد به ازای هر راس از $1$ تا $n$ پدرش در درخت نهایی را به او بگوید. یاسین که از برآورده کردن خواسته‌های پیرمرد‌ها و درخت‌هایشان خسته شده بود از شما می‌خواهد کمکش کنید تا خود را به بزرگ خاندان ثابت کند.

ورودی🔗

در خط اول ورودی $n$ می آید. $1 \leq n \leq 10^6$

سپس در خط $i$ ام از $n$ خط بعدی، سه عدد $t_i$ ، $p_i$ و $a_i$ به ترتیب آمده اند. $t_i \in \{1, 2\} ,\quad 0 \leq p_i < i, \quad 1 \leq a_i \leq n$

اگر $t_i$ برابر با $1$ بود این عملیات از نوع اول و اگر برابر با $2$ بود از نوع دوم است.

خروجی🔗

در تنها خط خروجی باید $n$ عدد چاپ کنید که عدد $i$ ام باید پدر راس $i$ در درخت نهایی باشد.

زیرمسئله‌ها🔗

زیرمسئله	نمره	محدودیت
۱	۷	$n \leq 5000$
۲	۱۲	$a_i \leq 2$
۳	۸۱	بدون محدودیت اضافی

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

5 1 0 1 3 3