Processing math: 0%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۹:تئوری:سوال ۶

سوال ۶

دنباله‌ی ‎a_1‎, ‎a_2‎, ‎\cdots‎, ‎a_n‎ از اعداد طبیعی به ما داده شده است. این دنباله را در زمان ‎O(n)‎ در یک داده ساختار طوری ذخیره کنید که هر بار عمل وارون کردن آن در زمان ‎O(\sqrt{n})‎ صورت گیرد. در عمل وارون کردن به ما دو عدد ‎i‎ و ‎j (i<j)‎ می‌دهند و از ما می‌خواهند که قسمت ‎a_i‎, ‎a_{i+1}‎, ‎\cdots‎, ‎a_j‎ در دنباله را وارون کنیم. یعنی دنباله‌ی ما بعد از این عمل تبدیل به ‎a_1‎, ‎a_2‎, ‎\cdots‎, ‎a_{i-1}‎, ‎a_{j}‎, ‎a_{j-1}‎, ‎\cdots‎, ‎a_{i}‎, ‎a_{j+1}‎, ‎a_{j+2}‎, ‎\cdots‎, ‎a_n‎ تبدیل می‌شود. دقت کنید که ممکن است از ما خواسته شود چندین بار عمل وارون را با مقادیر مختلف ‎i‎ و ‎j‎ روی دنباله انجام دهیم تا به دنباله‌های جدیدی برسیم و ما باید هر بار در ‎O(\sqrt{n})‎ این را انجام دهیم.


ابزار صفحه