http://codeforces.com/problemset/problem/455/D

There are a lot of ways to solve this problem.

(1) The most brutal way is to use square root decomposition.

(2) The more elegant way is to use splay trees or treaps to solve it.

Here I will only present the brutal way to solve it, i.e., using square root decomposition. Maybe some time later I will post

In this problem, we are asked to perform one operation and one query. For each operation, we are given two parameters l and r, and we need to perform a right shift on the interval from l to r, i.e. a[l]=a[r], a[l+1]=a[l], a[l+2]=a[l+1], …, a[r]=a[r-1]. For each query, we are given three parameters l, r and k, and we need to count the number of elements equal to k in the interval from l to r.

If we implement the data structure naively using a vector, each right shift operation would take O(n) time and each query would also take O(n) time, which would cause an overall complexity of O(nq) and consequentially lead us to “time limit exceeded”.

To implement a data structure with better performance, we can get help from a classical way called square root decomposition, i.e., dividing the elements into approximately sqrt(n) blocks each of which has approximately sqrt(n) elements. After that, we can keep for each block keep track of the elements inside it and the number of elements equal to 1 to 10^5 inside this block.

With this data structure, we can both perform the right shift operation in sqrt(n) steps and count the number of elements equal to k in an interval in sqrt(n) steps, since there can be at most sqrt(n) blocks and each block has at most sqrt(n) elements.

To perform each right shift operation, we can keep track of the elements inside each block in a deque (double ended queue) and insert the element positioned at r to position x and then push the right most element of the block which has just increased one in size to the following block until all blocks return to their normal size.

AC Code:

http://codeforces.com/contest/455/submission/35557449