Rope and Queries
Time limit0.3sMemory limit512 MB
Maintain a string under up to 100,000 queries that cut a substring and move it to the front or back, and print single characters.
- Level
Hard8 of 10
- Topics
- Linked list, Implementation, Simulation, Array
- Solved
- No attempts yet
Problem
Given a string S = S0S1...SN-1 of length N, perform the following queries.
- 1 x y: move SxSx+1...Sy to the front of the string. (0 ≤ x ≤ y < N)
- 2 x y: move SxSx+1...Sy to the back of the string. (0 ≤ x ≤ y < N)
- 3 x: print Sx. (0 ≤ x < N)
When S = "abcdefgh", the query 1 2 5 is performed as follows.
"abcdefgh" → "cdefabgh"
On the resulting string, the query 2 4 6 is performed as follows.
"cdefabgh" → "cdefhabg"
Input
The first line gives the string S. S consists only of lowercase English letters, and its length does not exceed 100,000.
The second line gives the number of queries Q (1 ≤ Q ≤ 100,000). Each of the next Q lines gives one query.
Output
For each query of type 3, print the answer. At least one query of type 3 is given.