Opis glavnog rešenja

Zadatak možemo rešiti naivno. U nizu \(a\) veličine \(n\) održavamo indikatore \(a_i\) (\(0 \leq i < n\)), pri čemu je \(a_i = 0\) ukoliko je karta na poziciji \(i\) okrenuta licem dole, a \(a_i = 1\) ukoliko je karta na poziciji \(i\) okrenuta licem gore. Niz \(a\) inicijalno popunimo nulama. Za upit prvog tipa, za svako \(i = l, \ldots, r\) ažuriramo \(a_i \gets \neg a_i\), dok za upit drugog tipa jednostavno ispišemo vrednost \(a_i\). Kod ovakvog pristupa za prvi tip upita vremenska složenost je \(O(n)\), dok je za drugi tip upita vremenska složenost \(O(1)\). Tada je ukupna složenost rešenja \(O(qn)\).

Bolje rešenje koristi niz \(f\) dužine \(n+1\). Inicijalno niz \(f\) popunimo nulama. Sa svaki upit prvog tipa uvećamo \(f_l\) za jedan i umanjimo \(f_{r + 1}\) za jedan. Tada važe sledeća tvrđenja:

Teorema 1: Nakon izvršavanja upita \(0 \, l \, r\), za svako \(k = l, \ldots, r\) važi da je prefiksna suma \(f_0 + f_1 + \ldots + f_k\) uvećana za jedan, dok će sve ostale prefiksne sume ostati iste. \(\blacksquare\)

Teorema 2: Ako je \(b_i\) broj okretanja karte na \(i\)-toj poziciji, onda je \(f_0 + f_1 + \ldots + f_i = b_i\), za svako \(i=0,\ldots,n-1\).

Dokaz: Fiksirajmo kartu na poziciji \(i\) i pokažimo tvrđenje indukcijom po broju izvršavanja upita prvog tipa.

• Inicijalno, nijedna karta nije okrenuta. Zbog toga, važi \(b_i = 0\). Takođe, važi da je niz \(f\) inicijalno popunjen nulama, te je \(f_0 + f_1 + \ldots + f_i = 0\).
• Pretpostavimo da za važi \(f_0 + f_1 + \ldots + f_i = b_i\) (1), pre izvršavanja upita \(0 \, l \, r\). Želimo da pokažemo da je \(f'_0 + f'_1 + \ldots f'_i = b'_i\) (2), gde je \(f'\) stanje niza nakon izvršavanja upita \(0 \, l \, r\) i \(b'_i\) novi broj okretanja karte na poziciji \(i\).
  • Ako je \(r < i\) ili \(i < l\), onda \(b'_i = b_i\) i iz teoreme 1 važi da \(f'_0 + f'_1 + \ldots f'_i = f_0 + f_1 + \ldots + f_i\). Zajedno sa pretpostavkom (1) sledi (2).
  • Ako je \(l < i < r\), onda \(b'_i = b_i + 1\) i iz teoreme 1 važi da \(f'_0 + f'_1 + \ldots f'_i = f_0 + f_1 + \ldots + f_i + 1\). Zajedno sa pretpostavkom (1) sledi (2). \(\blacksquare\)

Da bi odgovorili na drugi tip upita, zbog teoreme 2, jednostavno izračunamo prefiksnu sumu \(f_0 + f_1 + \ldots + f_i\) po modulu \(2\). Za efikasno ažuriranje i izračunavanje prefiksnih suma niz \(f\) implementiraćemo Fenvikovim stablom. Ukupna složenost ovakvog rešenja je \(O(q \log n)\).

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int BIT_sum(const vector<int> &bit, int k) 
{
    k++; // offset 1 from 0
         
    int sum = 0;
    while (k > 0) {
        sum += bit[k];
        k -= k & -k; // k = f(k)
    }
    return sum;
}

void BIT_update(vector<int> &bit, int k, const int x) 
{
    k++; // offset 1 from 0
    
    while (k <= bit.size()) {
        bit[k] += x;
        k += k & -k;
    }
}

int main(void) 
{
    int n, q; cin >> n >> q;

    vector<int> f(n + 2);

    while (q--) {
        int t; cin >> t;

        if (t == 0) {
            int l, r; cin >> l >> r;
            BIT_update(f, l, 1);
            BIT_update(f, r + 1, -1);
        } else { // t == 1
            int i; cin >> i;
            cout << BIT_sum(f, i) % 2 << endl;
        }
    }

    return 0;
}