I've used a treap with implicit keys, but I know only a Russian article about it (link). It's really interesting for me how to solve this problem without a treap.

I've attended the ACPC onsite , and there was an analysis session after the contest. The judges mentioned two solutions , one with the data structure you mention , and another one unrelated to it. I recall it involved reading all queries in advance then processing them in a backward manner. Maybe you can contact one of the judges if you are interested.

My idea: lets make list of chars with additional pointers at every T positions (not only at begin and at end of the list). Now we can find ith character in O(T) operations (take largest Q such that TQ<=i and move to ith character from that pointer in i-TQ operations), and add character in O(N/T)+O(T) operations (insert new character in the list at position P, and move every pointer that is at position Q, P<=Q, to the left).

If we take T=sqrt(N), then this solution works in O(N*sqrt(N)).

upd. 3451933 — here is the code.

I've solved it using only BIT. You just need to pre-process the queries in a reverse order so you can find the final string, then you'll already know for each query 'I' what's the position that R is suppose to be. This gives us O( |R|log²|R| ). Here is my solution: http://codepad.org/YQbQ0AOl