codeforces #297 B. Pasha and String

you can get the problem statement from here.

One important point we have to remember here is that if there are two update operation x, y (x < y < n/2) then the positions from y to n - y + 1 remain same as before the update operations.

One easy of looking the problem is as a simple lazy segment tree propagation problem O(n*log(n)). Using the segment tree's we have to record the number of swaps at each position. i.e we just have to perform the update operations(adding 1) in a lazy manner. and after that we have to swap the character if the number of swaps are odd.

but this problem can also solved in O(n). i.e counting the number of swaps.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s