Shared code

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <math.h>
#include <iomanip>
#include <queue>
#include <map>
#include <bitset>
#include <unordered_map>

#define LL long long
#define ULL unsigned long long
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define FORD(i, a, b) for (int i = (a) - 1; i >= (b); --i)
#define REPD(i, a, b) for (int i = (a); i >= (b); --i)
#define X first
#define Y second
#define pb(a) push_back(a);
#define pii pair<int, int>
#define pLi pair<LL, int>
#define piL pair<int, LL>
#define pLL pair<LL, LL>
#define ar array
#define ef else if

using namespace std;
const int mxn = 2e5 + 5;
const int MOD = 1e9 + 7;
const int BASE = 10000;
const int INF = 1000000000;
struct node
{
    int cnt, p;
    char x;
    bool flip;
    node *l, *r;

    node (char ch)
    {
        x = ch;
        flip = 0;
        cnt = 0;
        p = rand();
        l = r = NULL;
    }
};

int cnt (node *t)
{
    return (t ? t->cnt : 0);
}

void upd (node *t)
{
    if (!t) return;
    t->cnt = 1 + cnt(t->l) + cnt(t->r);
}

void down (node *t)
{
    if (!t || t->flip == 0) return;
    node *&l = t->l, *&r = t->r;
    swap(l, r);
    if (l) l->flip ^= 1;
    if (r) r->flip ^= 1;

    t->flip = 0;
}

void split (node *t, int key, node *&a, node *&b, int add = 0)
{
    if (!t) {a = b = NULL; return;}
    down(t);
    if (cnt(t->l) + 1 + add <= key)
    {
        split(t->r, key, t->r, b, add + cnt(t->l) + 1);
        a = t;
        upd(a);
    }
    else
    {
        split(t->l, key, a, t->l, add);
        b = t;
        upd(b);
    }
}

node *merge (node *a, node *b)
{
    if (!a || !b)
        return (a ? a : b);
    if (a->p <= b->p)
    {
        down(a);
        a->r = merge(a->r, b);
        upd(a);
        return a;
    }
    else
    {
        down(b);
        b->l = merge(a, b->l);
        upd(b);
        return b;
    }
}

void insert (node *&t, node *a)
{
    if (!t) { t = a; t->cnt = 1; }
    ef (t->p <= a->p)
    {
        insert(t->r, a);
        upd(t);
    }
    else
    {
        a->l = t;
        upd(a);
        t = a;
    }
}

void dfs (node *t)
{
    if (!t) return;
    down(t);
    dfs(t->l);
    cout << t->x;
    dfs(t->r);
}

void update (node *&t, int l, int r)
{
    node *a = NULL, *b = NULL, *c = NULL, *d = NULL;
    split(t, l - 1, a, b);
    split(b, r - l + 1, c, d);

    if (c) c->flip ^= 1;

    b = merge(c, d);
    t = merge(a, b);
}

int main()
{
    //freopen("D:\\test.txt", "r", stdin);
    //freopen("D:\\test2.txt", "w", stdout);
    int n, m;
    cin >> n >> m;
    char x;
    cin >> x;
    node *t = new node(x);

    REP(i, 2, n)
    {
        cin >> x;
        node *a = new node(x);
        insert(t, a);
    }

    REP(i, 1, m)
    {
        int l, r;
        cin >> l >> r;
        update(t, l, r);
    }

    dfs(t);
}