Editorial for Toggle and Count

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Türkçe

Soruyu çözmek için alttaki bilgileri tutan bir segment tree kullanmamız gerekli:

\(n0\): node'un belirttiği aralıktaki 0 rakamının sayısı.
\(n1\): node'un belirttiği aralıktaki 1 rakamının sayısı.
\(n01\): node'un belirttiği aralıktaki en büyük azalmayan altdizinin boyutu sayısı.
\(n10\): node'un belirttiği aralıktaki en büyük artmayan altdizinin boyutu sayısı.

Her toggle işleminde \(swap(n0, n1)\), \(swap(n01, n10)\) fonksiyonlarını çağırırız. Bu fonksiyonlar belirtilen aralıktaki 0'lar ve 1'lerin sayılarının yerini ve en büyük azalmayan altdizinin ve en büyük artmayan altdizinin boyutlarının yerini değiştirir. Her güncellemede şunları tutarız:

\(n0(father) = n0(left\_son) + n0(right\_son)\)
\(n01(father) = max(n01(left\_son) + n1(right\_son), n0(left\_son) + n01(right\_son), n0(left\_son) + n1(right\_son))\).

Bundan sonra count işlemlerinin cevabı \(n01\) olur.

English

To solve this problem you need to handle the segment tree with the following information:

\(n0\): number of 0-digits in node range.
\(n1\): number of 1-digits in node range.
\(n01\): maximum non-decreasing subsequence in range.
\(n10\): maximum non-increasing subsequence in range.

When the digits are toggled in some node \(swap(n0, n1)\), \(swap(n01, n10)\) are called. This swaps the count of 1's and 0's and the count of non-decreasing numbers with count of non increasing numbers. When we update node we keep:

\(n0(father) = n0(left\_son) + n0(right\_son)\)
\(n01(father) = max(n01(left\_son) + n1(right\_son), n0(left\_son) + n01(right\_son), n0(left\_son) + n1(right\_son))\).

Then for each count query result is \(n01\).

#include <bits/stdc++.h>
using namespace std;

#define MAX 2200010

struct Segment {
    int n0, n01, n10, n1;
    Segment() {}
    Segment(int v0, int v01, int v10, int v1) : n0(v0), n01(v01), n10(v10), n1(v1) {}
    Segment operator!() const {
        return Segment(n1, n10, n01, n0);
    }
};

Segment operator*(const Segment &a, const Segment &b) {
    return Segment(
        a.n0 + b.n0, 
        max(a.n01 + b.n1, a.n0 + b.n01), 
        max(a.n10 + b.n0, a.n1 + b.n10), 
        a.n1 + b.n1
    );
}

int N, M, segN;
string A;
Segment seg[MAX];
int tog[MAX];

void segPro(int a) {
    seg[a] = (tog[a << 1] ? !seg[a << 1] : seg[a << 1]) * (tog[a << 1 | 1] ? !seg[a << 1 | 1] : seg[a << 1 | 1]);
}

void segToggle(int a, int b) {
    int c, d;
    for (c = a += segN, d = b += segN; a <= b; a >>= 1, b >>= 1, c >>= 1, d >>= 1) {
        if (c != a) segPro(c);
        if (d != b) segPro(d);
        if ( a & 1) { tog[a] ^= 1; ++a; }
        if (~b & 1) { tog[b] ^= 1; --b; }
    }
    for (; c; c >>= 1, d >>= 1) {
        segPro(c);
        segPro(d);
    }
}

int main() {
    int i, a;
    char typ;

    cin >> N >> M >> A;
    for (segN = 1; segN < N; segN <<= 1);
    for (i = 0; i < segN; ++i) {
        seg[segN + i] = (i < N) ? (A[i] == '0') ? Segment(1, 1, 1, 0) : Segment(0, 1, 1, 1) : Segment(0, 0, 0, 0);
        tog[segN + i] = 0;
    }
    for (a = segN; --a; ) {
        segPro(a);
        tog[a] = 0;
    }
    for (; M--; ) {
        cin >> typ;
        if (typ == 't') {
            int a, b;
            cin >> a >> b;
            segToggle(a-1, b-1);
        } else {
            Segment res = tog[1] ? !seg[1] : seg[1];
            cout << res.n01 << endl;
        }
    }
}