Pošto je Draganče uspešno rešio sve zadatke koje mu je profesor Đurić zadao, matematika i programiranje su mu postali dosadni. Zato je odlučio da se malo za promenu posvetio hemiji. Pošto je svu potrebnu teoriju brzo savladao, rešio je da isproba kako sve to radi u praksi, pa je kupio spravu koja može da sastavlja jedinjenja po želji korisnika. Unutar sprave se nalazi traka koja je izdeljena na redom numerisana polja od 1 do N, i korisnik može da postavi atom na neko polje ili da ga ukloni. Na jednom polju trake može da se nalazi samo jedan atom. Ukoliko se dva atoma nalaze na susednim poljima, oni su spojeni.

Međutim, ono što sprava nema je provera stabilnosti jedinjenja. Naravno, Dragančetu to ne stvara problem, jer sve što mu je potrebno da bi izračunao stabilnost je da zna koliko je dugačak najduži lanac na nekom delu trake (lanac čine uzastopno povezani atomi). Kako broj atoma može biti veoma velik, a Draganče ne želi da provede ceo dan u brojanju atoma, zamolio je vas da mu pomognete u određivanju dužine najdužeg lanca na delu trake koji ga interesuje.

Ulaz:

(Ulazni podaci se nalaze u datoteci atomi.in) U prvom redu ulazne datoteke se nalaze dva broja, N i M. Broj N predstavlja dužinu trake, a M ukupan broj operacija. U narednih M linija nalaze se opisi operacija koje Draganče vrši, a operacije mogu biti:

• 0 i - (1 ≤ i ≤ N) uklanja atom sa polja i (ukoliko je polje već prazno, ništa se ne dešava)
• 1 i - (1 ≤ i ≤ N) postavlja atom na polje i (ukoliko se atom već nalazi na tom polju, ništa se ne dešava)
• 2 a b - (1 ≤ a ≤ b ≤ N) Draganče se pita kolika je dužina najdužeg lanca ako se posmatraju samo atomi koji se nalaze na intervalu [a,b].

Izlaz:

(Izlazne podatke upisati u datoteku atomi.out) Za svako pitanje (upit tipa "2 a b") u nov red datoteke treba ispisati odgovor.

Ograničenja:

• 1 ≤ N ≤ 1000000
• 1 ≤ M ≤ 500000
• vremensko ograničenje za izvršavanje programa je 1 s
• memorijsko ograničenje za izvršavanje programa je 32 MB

Primer 1:

8 5
1 3
1 5
2 3 5
1 4
2 1 8

1
3

Objašnjenje:

Posle druge operacije, traka izgleda ovako:
00X0X000
pa je odgovor 1.

Posle četvrte operacije traka izgleda ovako:
00XXX000
pa je odgovor 3.

Primer 2:

8 8
1 1
1 2
1 3
1 4
2 2 5
0 2
1 7
2 1 3

3
1

Objašnjenje:

Posle četvrte operacije traka izgleda ovako:
XXXX0000
ali pošto nas u petom pitanju zanima samo interval od polja 2 do polja 5, odgovor je 3.

Posle sedme operacije traka izgleda ovako :
X0XX00X0
pa je odgovor na osmo pitanje 1.

Napomena:

U 60% test primera će važiti M ≤ 1000.

1. O(M * N) - 60 poena

Najjednostavnije rešenje je da se u nizu pamti gde postoji atom a gde ne. Postavljanje i uklanjanje se vrši u O(1), dok je za odgovaranje na pitanje potrebno proći kroz ceo interval, što u najgorem slučaju može biti O(N).

2. O(M * sqrt(N)) - 80 poena

Celu traku ćemo izdeliti na segmente, tako da je dužina svakog segmenta sqrt(N) (ukoliko traka nije dovoljno dugačka, proširićemo je sa najviše sqrt(N) - 1 polja). Dakle, imamo sqrt(N) segmenata i svaki je dužine sqrt(N). Za svaki segment ćemo pamtiti tri informacije : koliko je dugačak lanac koji sadrži prvo polje segmenta, koliko je dugačak lanac koji sadrži poslednje polje segmenta (naravno, ukoliko se na tim mestima ne nalazi atom, dužina lanca je 0), i koliko je dugačak najduži lanac na celom intervalu. Neka Draganče zeli najduži lanac na intervalu [A,B]. Ukoliko A i B pripadaju istom segmentu, odgovor ćemo naći tako što ćemo proći kroz ceo interval. Zbog dužine segmenta, možemo imati najviše sqrt(N) iteracija. Pretpostavimo sada da A i B pripadaju segmentima S1 i S2. Na intervalu [A,poslednje_polje(S1)] ćemo naći najduži lanac, kao i dužinu lanca koji sadrži poslednje polje intervala S1 (nazvaćemo tu dužinu L), tako što ćemo proći kroz sva polja intervala. Dalje se nećemo kretati kroz svako polje, već ćemo samo posmatrati segmente u celini. Na dužinu L možemo nadovezati vrednost levo[S1+1]. Ukoliko je ceo segment S1+1 pokriven atomima, možemo nastaviti da nadovezujemo levo[S1+2], itd. U momentu kada dođemo do toga da segment S1 + k nije ceo pokriven atomima, L dobija vrednost desno[S1 + k], i nastavljamo dalje na isti način. Ovo kretanje po segmentima prekidamo kada dođemo do S2. Tada na dužinu L nadovežemo lanac koji sadrži polje prvo_polje(S2) i nalazi se u intervalu [prvo_polje(S2), B]. Takođe, na intervalu [prvo_polje(S2),B], nađemo i dužinu najdužeg lanca. Te dve stvari nalazimo tako što prođemo kroz svaki element intervala. Rešenje ce biti najveća dužina od svih posmatranih.

Prilikom postavljanja i uklanjanja atoma, da bi ažurirali informacije na segmentu, potrebno je da prođemo kroz svaki element tog segmenta, pa je složenost te dve operacije O(sqrt(N)). Kod odgovaranja na pitanje, u najgorem slučaju možemo posetiti sve elemente segmenta kome pripada A (njih ima sqrt(N)), sve segmente između segmenata kome pripadaju A i B (njih ima sqrt(N)-2), i sve elemente segmenta kome pripada B (njih ima sqrt(N)), pa je ukupna složenost O(sqrt(N)).

3. O(M * log N) - 100 poena

Prvo, proširićemo traku tako da broj elemenata bude stepen broja 2. Konstruisaćemo kompletno binarno stablo koje ima N listova (samim tim i dubinu log N). Svakom čvoru stabla ćemo pridružiti određen interval, i to na sledeći način : korenu stabla pridružujemo interval [1,N], njegovom levom sinu [1,N/2], a desnom [N/2 + 1, N], itd. Prema tome, listovima će odgovarati tačno jedan element, tj interval oblika [k,k]. Dalje, u svakom čvoru ćemo pamtiti još 4 informacije : koliko je dugačak lanac koji sadrži prvi element intervala koji odgovara tom čvoru, koliko je dugačak lanac koji sadrži poslednji element, kolika je dužina najdužeg lanca na tom intervalu, i da li je ceo interval pokriven atomima. Ažuriranje informacija posle uklanjanja/postavljanja atoma se vrši na sledeći način : u stablu nađemo list koji odgovara polju čije stanje menjamo (to možemo uraditi tako što ćemo se, počevši od korena, uvek kretati ka onom čvoru u čiji interval upada traženo polje). Ukoliko u to polje stavljamo atom, svim informacijama dodeljujemo vrednost 1, a ukoliko skidamo atom svim informacijama dodeljujemo vrednost 0. Kada promenimo informacije lista, to će uticati samo na njegove pretke (zbog načina na koji smo čvorovima dodeljivali intervale), pa ćemo samo njih posetiti, i to od dole ka gore (tj od lista ka korenu). Kako je dubina stabla log N, posetićemo tačno log N čvorova na putu od lista ka korenu. Neka se trenutno nalazimo u čvoru C, njegov levi sin je L a desni D. Informacije koje pamtimo u C računamo uz pomoć informacija iz L i D :

Ako je L.ceo_popunjen onda C.levo = L.levo + D.levo u suprotnom C.levo = L.levo; ako je D.ceo_popunjen onda C.desno = D.desno + L.desno u suprotnom C.desno = D.desno; C.najveci = max (L.najveci, D.najveci, L.desno + D.levo); C.ceo_popunjen ako je L.ceo_popunjen i D.ceo_popunjen; Prilikom traženja najdužeg lanca na datom intervalu konstruisaćemo pomoćno binarno stablo, koje ce po strukturi biti isto kao već opisano stablo. Traženje odgovora počinjemo od korena. Ukoliko je traženi interval upravo [1,N], odgovor već imamo kao informaciju koren.najveći. U suprotnom, rekurzivno tražimo koji čvorovi su odgovorni za traženi interval u levom i desnom podstablu. Pokazaćemo šta se radi u levom podstablu (desno podstablo se obrađuje na isti način): ukoliko smo došli do čvora kome je pridružen interval [p,q], i važi A ≤ p i q ≤ B, onda informacije iz tog čvora prepisujemo u novo stablo. U suprotnom, ako važi p ≥ B ili A ≥ q, svim informacijam u čvoru u novom stablu dodeljujemo vrednost 0. Inače, rekurzivno se spuštamo u levo i desno podstablo, i ponavljamo isti postupak. Po završetku obrađivanja levog i desnog podstabla, informacije računamo na isti način kao što smo radili i u prvobitnom stablu (naravno, ovde ne koristimo informacije prvobitnog stabla, već novog, pomocnog stabla). Na kraju, odgovor na pitanje koliko je dugačak najduži lanac na intervalu [A,B] će se nalaziti u informaciji "najveći" u korenu pomoćnog stabla. Složenost uklanjanja i postavljanja je O(log N). Prilikom traženja najdužeg lanca, interval [A,B] moze da se pokrije sa najviše log N čvorova, pa je i složenost O(log N). Prema tome, ukupna složenost je O(M * log N).

/*
ZADATAK: atomi
JEZIK: c++
*/

// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov

/*
resenje nosi 10 poena
vremenska slozenost : O(M * N)
prostorna slozenost : O(N)
*/

#include <iostream>
#include <cstdio>
using namespace std;

const long MaxN = 1000005;

long n, m;
bool postoji[MaxN];

FILE *fin, *fout;

int main(){
    fin=fopen("atomi.in","r");
    fout=fopen("atomi.out","w");

    memset(postoji,0,sizeof(postoji));
    fscanf(fin,"%ld %ld",&n,&m);
    long op,x,a,b;

    for (long k=0; k<m; k++){
        fscanf(fin,"%ld",&op);
        if (op == 0){
            fscanf(fin,"%ld",&x);
            postoji[x]=false;
        }
        else if (op == 1){
            fscanf(fin,"%ld",&x);
            postoji[x]=true;
        }
        else{
            fscanf(fin,"%ld %ld",&a,&b);

            long brojac=0, best=0;
            for (long i=a; i<=b; i++){
                if (postoji[i]) brojac++;
                else{
                    best=max(best,brojac);
                    brojac=0;
                }
            }
            best=max(best,brojac);
            fprintf(fout,"%ld\n",best);
        }
    }

    fclose(fin); fclose(fout);
    return 0;
}

/*
ZADATAK: atomi
JEZIK: c++
*/

// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov

/*
resenje nosi : 70 poena
vremenska slozenost : O(M * sqrt(N))
prostorna slozenost : O(N)
*/

#include <iostream>
#include <cstdio>
using namespace std;

const long MaxN = 1000005;
const long SqrtMaxN = 1005;

long n, m;
bool postoji[MaxN];
long levo[SqrtMaxN], desno[SqrtMaxN], najveci[SqrtMaxN];
long korak;

FILE *fin, *fout;

void update(long x){
    long mesto=x/korak;

    long nl=0;
    for (long i=mesto*korak; postoji[i] && i<(mesto+1)*korak; i++) nl++;
    levo[mesto]=nl;

    long nd=0;
    for (long i=(mesto+1)*korak - 1; postoji[i] && i>=mesto*korak; i--) nd++;
    desno[mesto]=nd;

    najveci[mesto]=0;
    long naj=0;
    for (long i=mesto*korak; i<(mesto+1)*korak; i++){
        if (postoji[i]) naj++;
        else{
            najveci[mesto]>?=naj;
            naj=0;
        }
    }
    najveci[mesto]>?=naj;
}

void dodaj(long x){
    postoji[x]=true;
    update(x);
}

void izbaci(long x){
    postoji[x]=false;
    update(x);
}

long prebroj(long a, long b){
    long reta = 0;
    long m1 = a/korak, m2= b/korak;
    if (m1 == m2){
        long brojac = 0;
        for (long i=a; i<=b; i++){
            if (postoji[i]) brojac++;
            else{
                reta>?=brojac;
                brojac=0;
            }
        }
        reta>?=brojac;
    }
    else{
        long brojac = 0;
        for (long i=a; i<(m1 + 1)*korak; i++){
            if (postoji[i]) brojac++;
            else{
                reta>?=brojac;
                brojac=0;
            }
        }
        for (long i=m1+1; i<m2; i++){
            reta>?=najveci[i];

            brojac+=levo[i];
            reta>?=brojac;

            if (levo[i]!=korak) brojac=desno[i];
        }
        for (long i=m2*korak; i<=b; i++){
            if (postoji[i]) brojac++;
            else{
                reta>?=brojac;
                brojac=0;
            }
        }
        reta>?=brojac;
    }

    return reta;
}

int main(){
    fin=fopen("atomi.in","r");
    fout=fopen("atomi.out","w");

    memset(postoji,0,sizeof(postoji));
    fscanf(fin,"%ld %ld",&n,&m);
  while (korak * korak < n) korak++;

    long op,x,a,b;
    for (long k=0; k<m; k++){
        fscanf(fin,"%ld",&op);
        if (op == 0){
            fscanf(fin,"%ld",&x);
            izbaci(x);
        }
        else if (op == 1){
            fscanf(fin,"%ld",&x);
            dodaj(x);
        }
        else{
            fscanf(fin,"%ld %ld",&a,&b);
            fprintf(fout,"%ld\n",prebroj(a,b));
        }
    }

    fclose(fin); fclose(fout);
    return 0;
}

/*
ZADATAK: atomi
JEZIK: c++
*/

// Atomi, SIO 2007
// Autor zadatka : Rajko Nenadov

/*
resenje nosi : 100 poena
vremenska slozenost : O(M * log N)
prostorna slozenost : O(N)
*/

#include <iostream>
#include <cstdio>
using namespace std;

const long MaxN = 1048576; // 2^20
const long MaxTree = MaxN * 2 + 1;

struct Cvor{
    long levo, desno, najveci;
    bool ceo;
};

Cvor tree[MaxTree], aux_tree[MaxTree];
long n, upper_n;
long m;

FILE *fin, *fout;

void make_tree(){
    for (long i=0; i<MaxTree; i++){
        tree[i].levo = 0; tree[i].desno = 0; tree[i].najveci = 0;
        tree[i].ceo = false;
    }
}

void update(long x){
    while (x>=1){
        long L1 = tree[2*x].levo, D1 = tree[2*x].desno, N1 = tree[2*x].najveci;
        bool C1 = tree[2*x].ceo;
        long L2 = tree[2*x + 1].levo, D2 = tree[2*x + 1].desno, N2 = tree[2*x + 1].najveci;
        bool C2 = tree[2*x + 1].ceo;

        if (C1) tree[x].levo = L1 + L2;
        else tree[x].levo = L1;

        if (C2) tree[x].desno = D2 + D1;
        else tree[x].desno = D2;

        tree[x].najveci = max(max(N1,N2), D1 + L2);

        tree[x].ceo = C1 && C2;

        x/=2;
    }
}

void dodaj(long x){
    tree[x].levo = 1; tree[x].desno = 1; tree[x].najveci = 1;
    tree[x].ceo = true;
    update(x/2);
}

void izbaci(long x){
    tree[x].levo = 0; tree[x].desno = 0;  tree[x].najveci = 0;
    tree[x].ceo = false;
    update(x/2);
}

void query(long ind, long p, long q, long a, long b){
    if (a<=p && q<=b){
        aux_tree[ind] = tree[ind];
    }
    else if (a>q ||p>b){
        aux_tree[ind].levo = 0; aux_tree[ind].desno = 0; aux_tree[ind].najveci = 0;
        aux_tree[ind].ceo = false;
    }
    else{
        query(ind*2, p, (p+q)/2, a, b);
        query(ind*2 + 1, (p+q)/2 + 1, q, a, b);

        long L1 = aux_tree[2*ind].levo, D1 = aux_tree[2*ind].desno, N1 = aux_tree[2*ind].najveci;
        bool C1 = aux_tree[2*ind].ceo;
        long L2 = aux_tree[2*ind + 1].levo, D2 = aux_tree[2*ind + 1].desno, N2 = aux_tree[2*ind + 1].najveci;
        bool C2 = aux_tree[2*ind + 1].ceo;

        if (C1) aux_tree[ind].levo = L1 + L2;
        else aux_tree[ind].levo = L1;

        if (C2) aux_tree[ind].desno = D2 + D1;
        else aux_tree[ind].desno = D2;

        aux_tree[ind].najveci = max(max(N1,N2), D1 + L2);

        aux_tree[ind].ceo = C1 && C2;
    }
}

int main(){
    fin=fopen("atomi.in","r");
    fout=fopen("atomi.out","w");

    fscanf(fin,"%ld %ld",&n,&m);
    upper_n = 1;
    while (upper_n<n) upper_n*=2;

    make_tree();
    long op,x,a,b;

    for (long k=0; k<m; k++){
        fscanf(fin,"%ld",&op);
        if (op == 0){
            fscanf(fin,"%ld",&x);
            izbaci(upper_n+x-1);
        }
        else if (op == 1){
            fscanf(fin,"%ld",&x);
            dodaj(upper_n+x-1);
        }
        else{
            fscanf(fin,"%ld %ld",&a,&b);
            query(1,1,upper_n,a,b);
            fprintf(fout,"%ld\n",aux_tree[1].najveci);
        }
    }

    fclose(fin); fclose(fout);
    return 0;
}