E. Sneetches and Speeches 2

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 3e5+5;

struct Treap {
   bool val, lazy1, lazy2;
   int max;
   bool vall, valr;
   int cntl, cntr;
   int pr, size;
   Treap *l, *r;
   Treap(bool val): val(val), lazy1(false), lazy2(false), max(1), vall(val), valr(val), cntl(1), cntr(1), size(1), l(nullptr), r(nullptr) {
      static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      pr = int(rng());
   }
};

int tsize(Treap *a) { return a ? a->size : 0; }
int tmax(Treap *a)  { return a ? a->max  : 0; }

Treap *tpropag(Treap *a) {
   if (!a) return nullptr;

   auto propag1 = [&]() {
      a->val  ^= true;
      a->vall ^= true;
      a->valr ^= true;

      if (a->l) a->l->lazy1 ^= true;
      if (a->r) a->r->lazy1 ^= true;
   };

   auto propag2 = [&]() {
      swap(a->cntl, a->cntr);
      swap(a->vall, a->valr);

      swap(a->l, a->r);

      if (a->l) a->l->lazy2 ^= true;
      if (a->r) a->r->lazy2 ^= true;
   };

   if (a->lazy1) propag1();
   if (a->lazy2) propag2();

   a->lazy1 = a->lazy2 = false;

   return a;
}

Treap *tupdate(Treap *a) {
   if (!a) return a;

   a->size = tsize(a->l) + tsize(a->r) + 1;

   tpropag(a);
   tpropag(a->l);
   tpropag(a->r);

   if (a->l && a->r) {
      bool lfull = tsize(a->l) == a->l->cntl;
      bool rfull = tsize(a->r) == a->r->cntr;

      if (lfull && rfull && a->val == a->l->val && a->val == a->r->val) {
         a->cntl = a->cntr = tsize(a);
         a->vall = a->valr = a->val;
         a->max = tsize(a);
      } else {
         a->cntl = a->l->cntl + (a->val == a->l->vall && lfull);
         a->cntr = a->r->cntr + (a->val == a->r->valr && rfull);

         if (a->val == a->l->valr && a->val == a->r->vall) {
            if (lfull)
               a->cntl += a->r->cntl;
            else if (rfull)
               a->cntr += a->l->cntr;
         }

         a->vall = a->l->vall;
         a->valr = a->r->valr;

         a->max = a->l->cntr * (a->l->valr == a->val) + 1 + a->r->cntl * (a->r->vall == a->val);
      }
   } else if (a->l) {
      a->cntl = a->l->cntl + (a->val == a->l->vall && a->l->cntl == tsize(a->l));
      a->cntr = a->l->cntr * (a->val == a->l->valr) + 1;

      a->vall = a->l->vall;
      a->valr = a->val;

      a->max = a->cntr;
   } else if (a->r) {
      a->cntl = a->r->cntl * (a->val == a->r->vall) + 1;
      a->cntr = a->r->cntr + (a->val == a->r->valr && a->r->cntr == tsize(a->r));

      a->vall = a->val;
      a->valr = a->r->valr;

      a->max = a->cntl;
   } else {
      a->cntl = a->cntr = 1;
      a->vall = a->valr = a->val;
      a->max = 1;
   }

   ckmax(a->max, tmax(a->l));
   ckmax(a->max, tmax(a->r));

   return a;
}

ostream &operator<<(ostream &out, Treap *treap) {
   function<void(Treap*)> dfs = [&](Treap *treap) {
      if (!treap) return;
      treap = tpropag(treap);
      dfs(treap->l);
      out << treap->val;
      dfs(treap->r);
   };
   dfs(treap);
   return out;
}

Treap *join(Treap *a, Treap *b) {
   if (!a || !b) return a ? a : b;
   tpropag(a);
   tpropag(b);
   if (a->pr < b->pr) return a->r = join(a->r, b), tupdate(a);
   return b->l = join(a, b->l), tupdate(b);
}

Treap *join(vector<Treap*> v) {
   if (v.empty()) return nullptr;
   Treap *ret = v[0];
   for (int i = 1; i < sz(v); i++)
      ret = join(ret, v[i]);
   return ret;
}

pair<Treap*, Treap*> split(Treap *a, int size) {
   if (!a) return { nullptr, nullptr };
   tpropag(a);
   if (tsize(a->l) + 1 <= size) {
      auto [ l, r ] = split(a->r, size - tsize(a->l) - 1);
      a->r = l;
      return { tupdate(a), r };
   }
   auto [ l, r ] = split(a->l, size);
   a->l = r;
   return { l, tupdate(a) };
}

int n, q;
char a[NMAX];

void read() {
   cin >> n >> q >> (a + 1);
}

tuple<Treap*, Treap*, Treap*> split_segment(Treap *treap, int l, int r) {
   auto [ a, suff ] = split(treap, l - 1);
   auto [ mid, b  ] = split(suff, r - l + 1);
   return { a, mid, b };
}

Treap *update1(Treap *treap, int l, int r) {
   auto [ a, mid, b ] = split_segment(treap, l, r);
   mid->lazy1 ^= true;
   return join({ a, mid, b });
}

Treap *update2(Treap *treap, int l, int r) {
   auto [ a, mid, b ] = split_segment(treap, l, r);
   mid->lazy2 ^= true;
   return join({ a, mid, b });
}

void solve() {
   Treap *treap = new Treap(a[1] - '0');
   for (int i = 2; i <= n; i++) {
      treap = join(treap, new Treap(a[i] - '0'));
   }

   while (q--) {
      int t, l, r;
      cin >> t >> l >> r;
      if (t == 1) {
         treap = update1(treap, l, r);
      } else if (t == 2) {
         treap = update2(treap, l, r);
      }
      tupdate(treap);
      cout << tmax(treap) << endl;
   }
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   solve();

   return 0;
}