Treap swap

#include <bits/stdc++.h>

using namespace std;

#define For(i, n)           for(int i = 0; i < n; ++i)
#define all(x)              (x).begin(),(x).end()
#define rall(x)             (x).rbegin(),(x).rend()
#define ls(x)               x+x+1
#define rs(x)               x+x+2
#define endl                '\n'

#define ld                  long double
#define pii                 pair<int, int>
#define vt                  vector
#define ll                  long long

template<typename T> void read(vt<T> & a) {For(i, a.size()) cin >> a[i];}
template<typename T> void read2(vt<vt<T> > & a) {For(i, a.size()) read(a[i]);}
template<typename T> void print(vt<T> & a) {For(i, a.size()) cout << a[i] << " "; cout << endl;}
template<typename T> void print2(vt<vt<T> > & a) {For(i, a.size()) print(a[i]);}

const int MAX = 1e9;
const int MOD = 1000000007;
const ll  INF = 1e18;
const ld  PI  = 3.14159265358979323846;

mt19937 rnd;

struct Node {
    ll sum, pref, suff, ans;
    Node() {
        this->sum = this->pref = this->suff = this->ans = 0;
    }
    Node(ll value) {
        this->sum = value;
        this->pref = this->suff = this->ans = max(0LL, value);
    }
};

Node merge(Node n1, Node n2) {
    Node r;
    r.sum = n1.sum + n2.sum;
    r.pref = max (n1.pref, n1.sum + n2.pref);
    r.suff = max (n2.suff, n2.sum + n1.suff);
    r.ans = max (max (n1.ans, n2.ans), n1.suff + n2.pref);
    return r;
}

struct Treap {
    Node data;
    ll value;
    int priority;
    array<Treap*, 2> kids;
    int subtree_size;

    Treap(int data);
};

int size(Treap *me) {
    return me == nullptr ? 0 : me->subtree_size;
}

void recalc(Treap *me) {
    if (me==nullptr) return;
    me->subtree_size = 1;
    Node result = Node();
    if (me->kids[0] != nullptr) {
        result = merge(result, me->kids[0]->data);
        me->subtree_size += me->kids[0]->subtree_size;
    }
    result = merge(result, Node(me->value));
    if (me->kids[1] != nullptr) {
        result = merge(result, me->kids[1]->data);
        me->subtree_size += me->kids[1]->subtree_size;
    }
    me->data = result;
}

Treap* merge(Treap *l, Treap *r) {
    if (l==nullptr) return r;
    if (r==nullptr) return l;
    if (l->priority < r->priority) {
        l->kids[1]=merge(l->kids[1], r);
        recalc(l);
        return l;
    }
    else {
        r->kids[0]=merge(l, r->kids[0]);
        recalc(r);
        return r;
    }
}

array<Treap*, 2> split(Treap *me, int nInLeft) {
    if (me == nullptr) return {nullptr, nullptr};
    if (size(me->kids[0])>=nInLeft) {
        array<Treap*, 2> leftRes=split(me->kids[0], nInLeft);
        me->kids[0]=leftRes[1];
        recalc(me);
        return {leftRes[0], me};
    }
    else {
        nInLeft = nInLeft - size(me->kids[0]) - 1;
        array<Treap*, 2> rightRes = split(me->kids[1], nInLeft);
        me->kids[1] = rightRes[0];
        recalc(me);
        return {me, rightRes[1]};
    }
    return {nullptr, nullptr};
}

Treap::Treap(int value) {
    kids={nullptr, nullptr};
    this->value = ((value == 0) ? -MAX : value);
    this->data = Node(this->value);
    this->priority = rnd();
    this->subtree_size = 1;
    recalc(this);
}

template<class F>
void each(Treap *n, F f) {
    if (n) { each(n->kids[0], f); f(n); each(n->kids[1], f); }
}

// https://codeforces.com/gym/102787/problem/Y

void solve() {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    Treap *root = nullptr;
    Treap *iroot = nullptr;
    For(i, n) {
        Treap *t = new Treap(s[i] - '0');
        Treap *it = new Treap((s[i] - '0') ^ 1);
        root = merge(root, t);
        iroot = merge(iroot, it);
    }
    For(i, q) {
        int _, l, r; cin >> _ >> l >> r;
        auto [other, third] = split(root, r);
        auto [first, second] = split(other, l - 1);

        auto [iother, ithird] = split(iroot, r);
        auto [ifirst, isecond] = split(iother, l - 1);


        root = merge(first, merge(isecond, third));
        iroot = merge(ifirst, merge(second, ithird));

        ll ans = max(root->data.ans, iroot->data.ans);
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}