المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

دنباله‌ی ‎$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})$‎ این را انجام دهیم.


ابزار صفحه