You can use Treap or Sqrt-decomposition. To make cyclic shift to right you should put last K elements to the beggining of the segment. You can do it using split operation.

Can be done with implicit treap (if you don't know what that is, go look it up).

Then first query (cyclic shifting to right) can be done as follows:

1. Get the treap corresponding for [L, R] (2 splits). Lets call this treap M.
2. Split treap M into two treaps M_L and M_R, such that M_R consists of the last K elements.
3. Merge treaps M_R|M_L into M (in this "reversed" order)
4. Insert M back to the general treap (2 merges).

Obviously the complexity will be .

The second operation is equivalent to cyclic shifting to right with R - L + 1 - K.

The last query can be easily done with 2 splits and 2 merges or by simply by traversing the treap.

The overall complexity will be .

PS: You can do this with sqrt decomposition (as you can easily perform split/merge with sqrt decomposition). That way the complexity for a cyclic shift will be and for the query .

My sqrt-decomposition code It's basically maintaining a doubly-linked list in O(sqrtN) time