Cut and Paste - Implementation

Here's the solution:

function solve(s, queries)
    // Build implicit treap from string
    root := null
    for i from 0 to length(s) - 1
        root := merge(root, createNode(s[i], randomPriority()))

    for each (l, r) in queries
        // 0-indexed: move [l-1, r-1] to end
        (left, temp) := splitBySize(root, l - 1)
        (mid, right) := splitBySize(temp, r - l + 1)
        root := merge(merge(left, right), mid)

    // Output final string via in-order traversal
    printInOrder(root)

Time: $O((n + q) \log n)$. Space: $O(n)$.