Palavra.cpp

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

int N, Q, K;

// Informacoes dos nos
vector<int> seg, peso;
vector<int> e, d, pai;
vector<bool> developed;

vector<int> seq;
set<int> avail; // Guarda nos que posso usar

int create() // Retorna no que posso usar (ou cria um se nao tiver)
{
    if (avail.empty())
    {
        seg.push_back(0);
        peso.push_back(0);
        e.push_back(0);
        d.push_back(0);
        developed.push_back(0);
        pai.push_back(0);
        avail.insert((int)seg.size()-1);
    }
    
    int pos = *avail.begin(); avail.erase(avail.begin());
    seg[pos] = 0;
    peso[pos] = 0;
    e[pos] = 0;
    d[pos] = 0;
    developed[pos] = 0;
    pai[pos] = 0;
    
    return pos;
}

void eraseSub(int pos) // Apaga subarvore de pos, exceto pos
{
    developed[pos] = 0;
    if (e[pos] != 0) {eraseSub(e[pos]); avail.insert(e[pos]);}
    if (d[pos] != 0) {eraseSub(d[pos]); avail.insert(d[pos]);}
    e[pos] = 0;
    d[pos] = 0;
}

void refresh(int pos) // Atualiza o no pos
{
    if (pos == 0) {seg[pos] = 0; peso[pos] = 0; return;}
    seg[pos] = min(seg[e[pos]] + peso[e[pos]], seg[d[pos]] + peso[d[pos]]);
}

void build(int pos, int nivel, int par) // funcao para construir a arvore
{
    eraseSub(pos); developed[pos] = 1;
    if (nivel >= 21 || par >= N) return;
    if (e[pos] == 0) {int aux = create(); e[pos] = aux;}
    if (d[pos] == 0) {int aux = create(); d[pos] = aux;}
    
    int expNivel = (1 << nivel);
    vector<int> viz = {e[pos], d[pos]};
    pai[e[pos]] = pai[d[pos]] = pos;

    for (int i = 0; expNivel*i + par < N; i++)
    {
        int id = expNivel * i + par;
        if (seq[id] <= nivel) continue;
        int chosenViz = 0;
        if (nivel+1 == seq[id]) chosenViz = ((id >> nivel)&1);
        else chosenViz = !((id>>nivel)&1);
        peso[viz[!chosenViz]]++;
    }

    if (peso[viz[0]] <= K) build(viz[0], nivel + 1, par + expNivel);
    if (peso[viz[1]] <= K) build(viz[1], nivel + 1, par);
    refresh(viz[0]); refresh(viz[1]); refresh(pos);
}

int update(int pos, int nivel, int x, int id, int val, bool &willBuild) //pos na seg, nivel na arvore, nivel que quero chegar, id na seq, val pra atualizar
{
    if (nivel == x || !developed[pos]) return pos;
    vector<int> viz = {e[pos], d[pos]};
    int chosenViz = 0;
    if (nivel+1 == x) chosenViz = (id&1);
    else chosenViz = !(id&1);
    peso[viz[!chosenViz]] += val;
    if (!developed[viz[chosenViz]] && peso[viz[chosenViz]] <= K) willBuild = 1;
    if (!developed[viz[!chosenViz]] && peso[viz[!chosenViz]] <= K) willBuild = 1;
    return update(viz[chosenViz], nivel+1, x, id>>1, val, willBuild);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // Crio dois nos iniciais, similar a Seg Dinamica
    create(); create();
    
    cin >> N >> Q >> K;
    
    seq.resize(N);
    for (auto &x : seq) cin >> x;
    for (auto &x : seq) x = min(x, 21);

    build(1, 0, 0);

    cout << (seg[1] <= K) << '\n';
    
    while (Q--)
    {
        int i, X;
        cin >> i >> X; --i; X = min(X, 21);
        
        int pos = 1, id = i, par = 0, type = 0, niv = 0;
        bool willBuild = false; // guarda se preciso refazer o build
       
        for (int nivel = 0; nivel <= 21; nivel++, niv++)
        {
            if (nivel == X || nivel == seq[i] || !developed[pos])
            {
                if (nivel == X) type = 1;
                else if (nivel == seq[i]) type = 2;
                break;
            }
            
            vector<int> viz = {e[pos], d[pos]};

            int chosenOld = 0, chosenNew = 0;
            if (nivel+1 == X) chosenNew = (id&1);
            else chosenNew = !(id&1);
            if (nivel+1 == seq[i]) chosenOld = (id&1);
            else chosenOld = !(id&1);

            if (chosenNew == chosenOld) {pos = viz[chosenNew]; id >>= 1; par += (1-chosenNew)*(1 << nivel); continue;}

            if (!developed[viz[chosenOld]] && (peso[viz[chosenOld]]+1) <= K){ willBuild = 1; break; }
            if (!developed[viz[chosenNew]] && (peso[viz[chosenNew]]-1) <= K){ willBuild = 1; break; }
            break;
        }

        int pos1 = update(pos, niv, seq[i], id, -1, willBuild);
        int pos2 = update(pos, niv, X, id, +1, willBuild);

        while (pos1 != pos)
        {
            pos1 = pai[pos1];
            refresh(e[pos1]); refresh(d[pos1]);
            refresh(pos1);
        }
        
        while (pos2 != pos)
        {
            pos2 = pai[pos2];
            refresh(e[pos2]); refresh(d[pos2]);
            refresh(pos2);
        }
        
        seq[i] = X;
        
        // Dou rebuild se necessario
        if (willBuild) build(pos, niv, par);
        
        while (pos != 1)
        {
            pos = pai[pos];
            refresh(e[pos]); refresh(d[pos]);
            refresh(pos);
        }

        cout << (seg[1] <= K) << '\n';
    }
}