Shared code

// CSES: Shrimb
#include"bits/stdc++.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template<class x>
using ordered_set = tree<x, null_type,less<x>,  rb_tree_tag,tree_order_statistics_node_update>;
 
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
 
struct String {
    string contents;
    int size, blocksize, splitCount;
    vector<array<int,2>> intervals; // {int l, int r, bool reversed}
 
    void Construct (const string &contents) {
        this -> contents = contents;
        size = contents.size();
        blocksize = sqrt(size) + 1;
        splitCount = 0;
        intervals = {{0, size - 1}};
    }
 
    String (string contents) {
        Construct(contents);
    }
 
    void rebuild () {
        string cpy(size, ' '); 
 
        const int numberOfIntervals = intervals.size();
 
        for (int i = 0, k = 0 ; i < numberOfIntervals ; i++) {
            auto [l, r] = intervals[i];
            if (l <= r) {
                for (int j = l ; j <= r ; j++, k++) cpy[k] = contents[j];
            } else { 
                for (int j = l ; j >= r ; j--, k++) cpy[k] = contents[j];
            }
        }
 
        Construct(cpy);
    }
 
    int split (int p) { 
 
        const int numberOfIntervals = intervals.size();
 
        for (int i = 0, j = 0 ; i < numberOfIntervals ; i++) {
 
            const auto [l, r] = intervals[i];
            const bool rev = (r < l);
            const int len = abs(r - l) + 1;
 
            if (p >= j && p < j + len) {
                if (rev) {
                    if (p != j && p != j + len - 1) {
                        intervals[i][0] -= p - j + 1;
                        intervals.insert(intervals.begin() + i, {array<int,2>{l, l - (p - j) + 1}, array<int,2>{l - (p - j), l - (p - j)}});
                        return i + 1;
                    } else if (p == j) {
                        if (len == 1) return i;
                        else {
                            intervals[i][0]--;
                            intervals.insert(intervals.begin() + i, array<int,2>{l, l});
                            return i;
                        }
                    } else {
                        intervals[i][1]++;
                        intervals.insert(intervals.begin() + i + 1, array<int,2>{r, r});
                        return i + 1;
                    }
                } else {
                    if (p != j && p != j + len - 1) {
                        intervals[i][0] += p - j + 1;
                        intervals.insert(intervals.begin() + i, {array<int,2>{l, l + (p - j) - 1}, array<int,2>{l + (p - j), l + (p - j)}});
                        return i + 1;
                    } else if (p == j){
                        if (len == 1) return i;
                        else {
                            intervals[i][0]++;
                            intervals.insert(intervals.begin() + i, array<int,2>{l, l});
                            return i;
                        }
                    } else {
                        intervals[i][1]--;
                        intervals.insert(intervals.begin() + i + 1, array<int,2>{r, r});
                        return i + 1;
                    }
                } 
            }
 
            j += len;
        }
        assert(0);
        return -1;
    }   
 
    void reverse (int l, int r) {
 
        if ((splitCount+=2) == blocksize) {
            rebuild();
            splitCount = 0;
        }
 
        int numberOfIntervals = intervals.size();
        
        int revL = split(l);
        int revR = split(r);
 
        numberOfIntervals = intervals.size();
 
 
        int sz = 0;
 
        for (int i = 0 ; i < numberOfIntervals ; i++) {
            const auto [L, R] = intervals[i];
            // cerr << "dbg: " << L << ' ' << R << endl;
            const int D = (L > R ? L - R : R - L) + 1;
            if (l >= sz && l < sz + D) {
                revL = i;
            } 
            if (r >= sz && r < sz + D) {
                revR = i;
            } 
            sz += D;
        }
 
        // cerr << "end: " << numberOfIntervals << ": " << revL << ' ' << revR << endl;
 
        std::reverse(intervals.begin() + revL, intervals.begin() + revR + 1);
 
        for (int i = revL ; i <= revR ; i++) {
            swap(intervals[i][0], intervals[i][1]);
        }
    }
};
 
signed main () {
    cin.tie(0) -> sync_with_stdio(0);
 
    int n, q;
    cin >> n >> q;
 
    string s;
 
    cin >> s;
 
    String t(s);
 
    while (q--) {
        int l, r;
        cin >> l >> r;
        t.reverse(l - 1, r - 1);
    }
 
    t.rebuild();
 
    cout << t.contents << endl;
    
}