LogoArhiva Educațională
AcasaUsorMediuDificilAvansatOlimpiada de InformaticaIntroducere în C++AIBacalaureat

Sparse Table. Binary Lifting. Range Minimum Query (RMQ)

Introducere

Sparse Table este o structură de date care ne ajută, în principal, să răspundem la întrebări pe un interval, fiecare răspuns fiind calculat în O(log⁡n)\mathcal{O}(\log n) (mai puțin atunci când folosim RMQ, despre care o să discutăm mai târziu în acest articol).

Sparse Table. Binary Lifting

Să luăm ca exemplu problema Static Range Sum Queries de pe CSES. Desigur că o putem rezolva folosind sume parțiale, dar haideți să încercăm o metodă nouă.

Fie spti,jspt_{i, j} suma numerelor din intervalul [j,j+2i)[j, j + 2^i). Când avem o întrebare pe intervalul [st,dr][st, dr], îl vom împărți în intervale de lungimi puteri de 2. Lungimile acestor intervale vor fi egale cu biții din reprezentarea în baza 2 a lui dr−st+1dr - st + 1. Această metodă se cheamă binary lifting.

Atenție

Este foarte important ca, în spti,jspt_{i, j}, 2i2^i să fie lungimea intervalului și jj să fie primul element. Dacă implementăm altfel, timpul implementării va crește foarte mult. Unoeri, acest lucru poate duce și la TLE. Mai multe detalii puteți găsi în acest blog.

Observație

LCA este calculat, de asemenea, folosind binary lifting. Căutarea binară în AIB folosește, de asemenea, binary lifting.

Sursa de 100:

#include <iostream>

const int MAXN = 200'000;
const int LOGN = 18;

int v[MAXN], n, q;

struct SparseTable {
    long long spt[LOGN][MAXN];
    int maxbit;

    void init(int n) {
        int i, j;
        for (i = 0; i < n; i++) {
            spt[0][i] = v[i];
        }
        maxbit = 31 - __builtin_clz(n);  // i-ul maxim
        for (i = 1; i <= maxbit; i++) {
            for (j = 0; j + (1 << i) - 1 < n; j++) {
                spt[i][j] = spt[i - 1][j] + spt[i - 1][j + (1 << (i - 1))];
            }
        }
    }

    long long query(int st, int dr) {
        int len = dr - st + 1, i;
        long long sum = 0;
        for (i = maxbit; i >= 0; i--) {
            if (len & (1 << i)) {  // daca are bitul i
                sum += spt[i][st];
                st += 1 << i;
            }
        }
        return sum;
    }
} table;

void readArray() {
    int i;
    std::cin >> n >> q;
    for (i = 0; i < n; i++) {
        std::cin >> v[i];
    }
}

void answerQueries() {
    int i, st, dr;
    for (i = 0; i < q; i++) {
        std::cin >> st >> dr;
        std::cout << table.query(st - 1, dr - 1) << "\n";
    }
}

int main() {
    readArray();
    table.init(n);
    answerQueries();
    return 0;
}

Range Minimum Query

Așa cum îi spune și numele, la Range Minimum Query (RMQ), avem întrebări la care trebuie să răspundem cu minimul pe un interval. Vom folosi un sparse table.

Ideea principală la RMQ este să împărțim intervalul [st,dr][st, dr] în două intervale: [st,st+2lg),(dr−2lg,dr][st, st + 2^{lg}), (dr - 2^{lg}, dr] (unde lglg reprezintă cel mai mare număr astfel încât 2lg≤dr−st+12^{lg} \leq dr - st + 1). Aceste intervale au lungimea 2lg2^{lg}, deci le putem afla răspunsurile în O(1)\mathcal{O}(1) (deoarece le avem deja precalculate).

Observație

Noi repetăm elementele din intervalul (st+2lg,dr−2lg)(st + 2^{lg}, dr - 2^{lg}). Acest lucru nu ne afectează, deoarece min(x,x)=xmin(x, x) = x.

Observație

Vom precalcula un vector lg2i=lg2_i = cel mai mare jj astfel încât 2j≤i2^j \leq i. Acest vector ne va ajuta să calculăm lglg ușor.

Tabloul sptspt se calculează la fel ca înainte.

Sursa de accepted (la problema Static Range Minimum Queries):

#include <iostream>

const int MAXN = 200'000;
const int LOGN = 18;

int v[MAXN], n, q;

int min(int a, int b) { return a < b ? a : b; }

struct SparseTable {
    int spt[LOGN][MAXN], lg2[MAXN + 1];

    void init(int n) {
        int i, j;
        for (i = 2; i <= n; i++) {
            lg2[i] = 1 + lg2[i >> 1];
        }
        for (i = 0; i < n; i++) {
            spt[0][i] = v[i];
        }
        for (i = 1; i <= lg2[n]; i++) {
            for (j = 0; j + (1 << i) - 1 < n; j++) {
                spt[i][j] = min(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int query(int st, int dr) {
        int lg = lg2[dr - st + 1];
        return min(spt[lg][st], spt[lg][dr - (1 << lg) + 1]);
    }
} rmq;

void readArray() {
    int i;
    std::cin >> n >> q;
    for (i = 0; i < n; i++) {
        std::cin >> v[i];
    }
}

void answerQueries() {
    int i, st, dr;
    for (i = 0; i < q; i++) {
        std::cin >> st >> dr;
        std::cout << rmq.query(st - 1, dr - 1) << "\n";
    }
}

int main() {
    readArray();
    rmq.init(n);
    answerQueries();
    return 0;
}

Observație

RMQ poate fi folosit cu orice operație ff care este idempotentă, adică f(x,x)=xf(x, x) = x (minim, maxim, cmmdc etc). Avem nevoie de acest lucru, deoarece, cum am observat mai sus, noi repetăm anumite elemente.

RMQ 2D

Putem face RMQ și pe matrice. Să luam ca exemplu problema CF 713D.

Să calculăm, mai întâi maxpi,j=maxp_{i, j} = latura celui mai mare dreptunghi care are doar valori de 1 și are colțul dreapta-jos în (i,j)(i, j). Această metodă se cheamă programare dinamică.

maxpi,j={0daca˘ i=0 sau j=00daca˘ i,j>0 și ai,j=0min(maxpi−1,j,maxpi,j−1,maxpi−1,j−1)+1daca˘ i,j>0 și ai,j=1maxp_{i, j} = \begin{cases} 0 &\text{dacă } i = 0 \text{ sau } j = 0 \\ 0 &\text{dacă } i, j > 0 \text{ și } a_{i, j} = 0 \\ min(maxp_{i-1, j}, maxp_{i, j-1}, maxp_{i-1, j-1}) + 1 &\text{dacă } i, j > 0 \text{ și } a_{i, j} = 1 \end{cases}

Acum, să vedem cum se calculează sptspt. Fie spti,j,l,c=spt_{i, j, l, c} = maximul elementelor din submatricea cu colțul stânga-sus la (i,j)(i, j) și cu colțul dreapta-jos la (l+2i−1,c+2j−1)(l+2^i-1, c+2^j-1) din maxpmaxp.

spti,j,l,c={maxpl,cdaca˘ i=0,j=0max(spti−1,j,l,c,spti−1,j,l,c+2i−1)daca˘ i=0,j>0max(spti,j−1,l,c,spti,j−1,l+2i−1,c)daca˘ i>0,j=0max(spti−1,j−1,l,c,spti−1,j−1,l+2i−1,c,spti−1,j−1,l,c+2j−1,spti−1,j−1,l+2i−1,c+2j−1)daca˘ i,j>0spt_{i, j, l, c} = \begin{cases} maxp_{l, c} &\text{dacă } i = 0, j = 0 \\ max(spt_{i-1, j, l, c}, spt_{i-1, j, l, c + 2^{i-1}}) &\text{dacă } i = 0, j > 0 \\ max(spt_{i, j-1, l, c}, spt_{i, j-1, l + 2^{i-1}, c}) &\text{dacă } i > 0, j = 0 \\ max(spt_{i-1, j-1, l, c}, spt_{i-1, j-1, l + 2^{i-1}, c}, spt_{i-1, j-1, l, c + 2^{j-1}}, spt_{i-1, j-1, l + 2^{i-1}, c + 2^{j-1}}) &\text{dacă } i, j > 0 \end{cases}

Să vedem cum se calculează răspunsul pentru o întrebare pe un dreptunghi cu colțul stânga-sus în (l1,c1)(l_1, c_1) și coltul dreapta-jos în (l2,c2)(l_2, c_2). Fie lgl=lgl = cel mai mare număr astfel încât 2lgl≤l2−l1+12^{lgl} \leq l_2-l_1+1 și lgc=lgc = cel mai mare număr astfel încât 2lgc≤c2−c1+12^lgc \leq c_2-c_1+1.

query(l1,c1,l2,c2)=max(sptlgl,lgc,l1,c1,sptlgl,lgc,l2−2lgl+1,c1,sptlgl,lgc,l1,c2−2lgc+1,sptlgl,lgc,l2−2lgl+1,c2−2lgc+1)query(l_1, c_1, l_2, c_2) = max(spt_{lgl, lgc, l_1, c_1}, spt_{lgl, lgc, l_2 - 2^{lgl} + 1, c_1}, spt_{lgl, lgc, l_1, c_2 - 2^{lgc} + 1}, spt_{lgl, lgc, l_2 - 2^{lgl} + 1, c_2 - 2^{lgc} + 1})

Mai departe, observăm că noi nu avem cum sa aflăm direct răspunsul, deoarece unele rezultate pot ieși din dreptunghiul în care suntem întrebați. Așa că, vom căuta binar răspunsul.

Cum verificăm dacă avem vreun pătrat de latură cel puțin kk? Vom verifica dacă:

query(l2−k+1,c2−k+1,l2,c−2)≥kquery(l_2-k+1, c_2-k+1, l_2, c-2) \geq k

Adică vom verifica dacă există vreun colț dreapta-jos care formează un pătrat de latură cel puțin kk.

Sursa de Accepted:

#include <iostream>

const int MAXN = 1'000;
const int LOGN = 11;

int mat[MAXN + 1][MAXN + 1], maxp[MAXN + 1][MAXN + 1], n, m;

int min(int a, int b) { return a < b ? a : b; }

int min(int a, int b, int c) { return min(min(a, b), c); }

int max(int a, int b) { return a > b ? a : b; }

int max(int a, int b, int c, int d) { return max(max(a, b), max(c, d)); }

struct SparseTable2D {
    int spt[LOGN][LOGN][MAXN + 1][MAXN + 1], lg2[MAXN + 1];

    void init() {
        int i, j, l, c;
        for (i = 2; i <= MAXN; i++) {
            lg2[i] = 1 + lg2[i >> 1];
        }
        for (l = 1; l <= n; l++) {
            for (c = 1; c <= m; c++) {
                spt[0][0][l][c] = maxp[l][c];
            }
        }
        for (i = 1; i <= lg2[n]; i++) {
            for (l = 1; l <= n; l++) {
                for (c = 1; c <= m; c++) {
                    spt[i][0][l][c] = max(spt[i - 1][0][l][c],
                                          spt[i - 1][0][l + (1 << (i - 1))][c]);
                }
            }
        }
        for (j = 1; j <= lg2[m]; j++) {
            for (l = 1; l <= n; l++) {
                for (c = 1; c <= m; c++) {
                    spt[0][j][l][c] = max(spt[0][j - 1][l][c],
                                          spt[0][j - 1][l][c + (1 << (j - 1))]);
                }
            }
        }
        for (i = 1; i <= lg2[n]; i++) {
            for (j = 1; j <= lg2[m]; j++) {
                for (l = 1; l + (1 << i) - 1 <= n; l++) {
                    for (c = 1; c + (1 << j) - 1 <= m; c++) {
                        spt[i][j][l][c] =
                            max(spt[i - 1][j - 1][l][c],
                                spt[i - 1][j - 1][l][c + (1 << (j - 1))],
                                spt[i - 1][j - 1][l + (1 << (i - 1))][c],
                                spt[i - 1][j - 1][l + (1 << (i - 1))]
                                   [c + (1 << (j - 1))]);
                    }
                }
            }
        }
    }

    int query(int l1, int c1, int l2, int c2) {
        int lgl = lg2[l2 - l1 + 1], lgc = lg2[c2 - c1 + 1];
        return max(spt[lgl][lgc][l1][c1],
                   spt[lgl][lgc][l1][c2 - (1 << lgc) + 1],
                   spt[lgl][lgc][l2 - (1 << lgl) + 1][c1],
                   spt[lgl][lgc][l2 - (1 << lgl) + 1][c2 - (1 << lgc) + 1]);
    }
} rmq2d;

void fastReadWrite() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
}

void readMatrix() {
    int l, c;
    std::cin >> n >> m;
    for (l = 1; l <= n; l++) {
        for (c = 1; c <= m; c++) {
            std::cin >> mat[l][c];
        }
    }
}

void computeMaxp() {
    int l, c;
    for (l = 1; l <= n; l++) {
        for (c = 1; c <= m; c++) {
            if (mat[l][c] == 0) {
                maxp[l][c] = 0;
            } else {
                maxp[l][c] =
                    1 + min(maxp[l - 1][c], maxp[l][c - 1], maxp[l - 1][c - 1]);
            }
        }
    }
}

void answerQueries() {
    int l1, c1, l2, c2, q, st, dr, mij;
    std::cin >> q;
    while (q--) {
        std::cin >> l1 >> c1 >> l2 >> c2;
        st = 0;  // intervalul este [) (inchis-deschis)
        dr = min(l2 - l1 + 1, c2 - c1 + 1)
           + 1;  // patratul maxim care este inclus
        while (dr - st > 1) {
            mij = (st + dr) / 2;
            if (rmq2d.query(l1 + mij - 1, c1 + mij - 1, l2, c2) >= mij) {
                st = mij;
            } else {
                dr = mij;
            }
        }
        std::cout << st << "\n";
    }
}

int main() {
    fastReadWrite();
    readMatrix();
    computeMaxp();
    rmq2d.init();
    answerQueries();
    return 0;
}

Reverse RMQ

Putem să rezolvăm și probleme în care avem doar actualizări, fără întrebări, adica o problemă în care avem actualizări de forma ai=max(ai,x)a_i = max(a_i, x), pentru l≤i≤rl \leq i \leq r. O putem rezolva asemănător, folosind aceleași intervale ca la RMQ normal și modificând astfel:

sptlg,st=max(sptlg,st,x)sptlg,dr−2lg+1=max(sptlg,dr−2lg+1,x)spt_{lg, st} = max(spt_{lg, st}, x) \\ spt_{lg, dr - 2^{lg} + 1} = max(spt_{lg, dr - 2^{lg} + 1}, x)

Apoi, valoarea aia_i finală va fi maximul dintre toate valorile din orice interval care este actualizat în sptspt și include ii. Calculăm această valoare folosind un proces similar cu propagarea lazy de la arbori de intervale. Rezultatul din spti,jspt_{i, j} va fi propagat doar în spti−1,jspt_{i - 1, j} și spti−1,j+2i−1spt_{i - 1, j + 2^{i-1}}, deoarece acestea sunt singurele intervale necesare pentru a ne asigura că rezultatul ajunge la toate pozițiile din șir. Pentru mai multe detalii vedeți implementarea.

Sursa de accepted (la problema Glad You Came de pe codeforces)

#include <iostream>

const int MAXN = 100'000;
const int MAXVAL = 1 << 30;
const int MAXLOG = 17;

int n;
unsigned int x, y, z;

int max(int a, int b) { return a > b ? a : b; }

struct SparseTable {
    int spt[MAXLOG][MAXN], lg2[MAXN + 1];

    void init(int n) {
        int i, j;
        for (i = 2; i <= n; i++) {
            lg2[i] = 1 + lg2[i >> 1];
        }
        for (i = 0; i <= lg2[n]; i++) {
            for (j = 0; j < n; j++) {
                spt[i][j] = 0;
            }
        }
    }

    void update(int st, int dr, int val) {
        int lg = lg2[dr - st + 1], dr_idx;
        spt[lg][st] = max(spt[lg][st], val);
        dr_idx = dr - (1 << lg) + 1;
        spt[lg][dr_idx] = max(spt[lg][dr_idx], val);
    }

    void pullResults() {
        int i, j, new_j;
        for (i = lg2[n]; i > 0; i--) {
            for (j = 0; j + (1 << i) <= n; j++) {
                spt[i - 1][j] = max(spt[i - 1][j], spt[i][j]);
                new_j = j + (1 << (i - 1));
                spt[i - 1][new_j] = max(spt[i - 1][new_j], spt[i][j]);
            }
        }
    }

    void writeAnswer() {
        int i;
        unsigned long long answer;
        pullResults();
        answer = 0;
        for (i = 0; i < n; i++) {
            answer ^= 1LL * (i + 1) * spt[0][i];
        }
        std::cout << answer << "\n";
    }
} rmq;

unsigned int nextValue() {
    unsigned int w;
    x ^= x << 11;
    x ^= x >> 4;
    x ^= x << 5;
    x ^= x >> 14;
    w = x ^ y ^ z;
    x = y;
    y = z;
    z = w;
    return z;
}

void processUpdates() {
    int q, i, st, dr, val, aux;
    std::cin >> n >> q >> x >> y >> z;
    rmq.init(n);
    for (i = 0; i < q; i++) {
        st = nextValue() % n;
        dr = nextValue() % n;
        if (st > dr) {
            aux = st;
            st = dr;
            dr = aux;
        }
        val = nextValue() % MAXVAL;
        rmq.update(st, dr, val);
    }
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        processUpdates();
        rmq.writeAnswer();
    }
    return 0;
}

RMQ sau Arbori de intervale?

Arborii de intervale (AINT) pot face tot ce poate face RMQ, dar haideți să comparăm aceste două structuri de date.

Comparație în funcție de timp

RMQ este precalculat, la început, în O(nlog⁡n)\mathcal{O}(n \log n), iar AINT în O(n)\mathcal{O}(n). Însă, RMQ are complexitate O(1)\mathcal{O}(1) per query, În timp ce AINT are O(log⁡n)\mathcal{O}(\log n) per query.

Comparație în funcție de memorie

RMQ folosește O(nlog⁡n)\mathcal{O}(n \log n) memorie, iar AINT folosește O(n)\mathcal{O}(n) memorie.

Alte precizări

AINT poate rezolva și alte probleme pe care RMQ nu le poate rezolva. La astfel de probleme, putem folosi un Sparse Table normal, rezultând aceeași complexitate ca la AINT la query-uri. Acest lucru înseamnă că AINT este mai folositor în acest caz, chiar dacă este mai greu de implementat.

În același timp, AINT poate trata și actualizări împreună cu interogări, iar RMQ nu le poate trata. În această situație, RMQ nu intră în calcul atunci când dorim să găsim cea mai bună structură de date pentru a rezolva o anumită problemă.

Concluzie

AINT este, de obicei, mai folositor ca RMQ, mai puțin atunci când numărul de query-uri este cu mult mai mare decât numărul de elemente sau atunci când dorim să nu scriem prea multe linii de cod.

Probleme rezolvate

Problema excursie

Kilonova

View Problem

Kilonova

Could not fetch problem details

Deschide

Observăm că indicatoarele trebuie să fie de forma RRR...RLLL..L. Să fixam poziția ii până la care vom avea R-uri. Costul va fi egal cu numărul de L-uri de la stst la ii adunat cu numărul de R-uri de la i+1i + 1 la drdr. Aceste lucruri pot fi calculate ușor folosind sume parțiale.

Fie prefLi=prefL_i = câte L-uri sunt de la 1 la ii și suffRi=suffR_i = câte R-uri sunt de la ii la nn. Atunci răspunsul va fi min(prefLi−prefLst−1+suffRi+1−suffRdr+1)min(prefL_i - prefL_{st-1} + suffR_{i+1} - suffR_{dr+1}) astfel încât st−1≤i≤drst - 1 \leq i \leq dr. Acest lucru este echivalent cu a afla minimul expresiei prefLi+suffRi+1prefL_i + suffR_{i+1} cu ii in intervalul [st−1,dr][st - 1, dr]. Vom folosi RMQ pentru a afla acest minim.

Sursa de 100 de puncte:

#include <ctype.h>

#include <fstream>

const int MAXN = 200'000;
const int LOGN = 18;

std::ifstream fin("excursie.in");
std::ofstream fout("excursie.out");

char v[MAXN + 1];
int n, prefL[MAXN + 1], suffR[MAXN + 2];

int min(int a, int b) { return a < b ? a : b; }

struct SparseTable {
    int spt[LOGN][MAXN + 1], lg2[MAXN + 2];

    void init() {
        int i, j;
        for (i = 2; i <= n + 1; i++) {
            lg2[i] = 1 + lg2[i >> 1];
        }
        for (i = 0; i <= n; i++) {
            spt[0][i] = prefL[i] + suffR[i + 1];
        }
        for (i = 1; i <= lg2[n]; i++) {
            for (j = 0; j + (1 << i) - 1 <= n; j++) {
                spt[i][j] = min(spt[i - 1][j], spt[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    int query(int st, int dr) {
        int lg = lg2[dr - st + 1];
        return min(spt[lg][st], spt[lg][dr - (1 << lg) + 1]);
    }
} rmq;

void readString() {
    int i, ch;
    fin >> n;
    while (!isalpha(ch = fin.get()))
        ;
    for (i = 1; i <= n; i++) {
        v[i] = (ch == 'R');
        ch = fin.get();
    }
}

void computePartialSums() {
    int i;
    for (i = 1; i <= n; i++) {
        prefL[i] = prefL[i - 1] + (1 - v[i]);
    }
    for (i = n; i > 0; i--) {
        suffR[i] = suffR[i + 1] + v[i];
    }
}

void answerQueries() {
    int q, i, st, dr, aux;
    fin >> q;
    for (i = 0; i < q; i++) {
        fin >> st >> dr;
        if (st > dr) {
            aux = st;
            st = dr;
            dr = aux;
        }
        fout << rmq.query(st - 1, dr) - prefL[st - 1] - suffR[dr + 1] << "\n";
    }
}

int main() {
    readString();
    computePartialSums();
    rmq.init();
    answerQueries();
    return 0;
}

Problema Yunli's Subarray Queries

Codeforces

View Problem

Codeforces

Could not fetch problem details

Deschide

Versiunea ușoară

Codeforces

View Problem

Codeforces

Could not fetch problem details

Deschide

Să rezolvăm mai întâi versiunea ușoară. Noi trebuie să avem bi=bi+1−1=bi+2−2=..=bi+k−1−(k−1)b_i = b_{i+1} - 1 = b_{i+2} - 2 = .. = b_{i+k-1} - (k-1). Să scădem ii din această relație: bi−i=bi+1−(i+1)=bi+2−(i+2)=..=bi+k−1−(i+k−1)b_i - i = b_{i+1} - (i+1) = b_{i+2} - (i+2) = .. = b_{i+k-1} - (i+k-1). Acest lucru este echivalent cu: ai=ai+1=ai+2=..=ai+k−1a_i = a_{i+1} = a_{i+2} = .. = a_{i+k-1}, unde $$$$$$$$a_i = b_i

  • i$$$$$$$$.

Să precalculam rezi=rez_i = frecvența elementului majoritar din intervalul $$[i, i

  • k)( (k - rez_lvafira˘spunsulnostrulaunquery).va fi răspunsul nostru la un query).rezpoate fi calculat folosind [sliding window](../mediu/sliding-window.mdx). Vom menține un [map](../cppintro/stl.mdx#structura-stdmap) care se cheamăfrcufrecvențaelementelorșiı^ncaun[vectordefrecvența˘](../usor/frequency−arrays.mdx)caresecheama˘cu frecvența elementelor și înca un [vector de frecvență](../usor/frequency-arrays.mdx) care se cheamăfrfrcaremenținefrecvențafieca˘reivaloridincare menține frecvența fiecărei valori dinfr$$$$$$$$.

Când adaugăm o valoare, scădem 1 din frfrfrvalfrfr_{fr_{val}}, creștem frvalfr_{val} cu 1 și adunăm 1 la noul frfrfrvalfrfr_{fr_{val}}. Dacă frvalfr_{val} este mai mare ca rezulatul curent, atunci setăm rezultatul curent la frvalfr_{val}.

Atunci când scoatem o valoare, scădem 1 din frfrfrvalfrfr_{fr_{val}}. Dacă frvalfr_{val} era egal cu rezultatul și frfrfrvalfrfr_{fr_{val}} a devenit 0, atunci rezultatul scade cu 1, deoarece frfrfrval−1frfr_{fr_{val} - 1} a crescut cu 1. Restul rămâne la fel ca la adăugare.

Sursa de accepted la G1:

#include <iostream>
#include <map>

const int MAXN = 200'000;

int n, k, q, result, a[MAXN], rez[MAXN], frfr[MAXN + 1];
std::map<int, int> fr;

void fastReadWrite() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
}

void readArray() {
    int i;
    std::cin >> n >> k >> q;
    for (i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i] -= i;
    }
}

void addValue(int val) {
    frfr[fr[val]]--;
    fr[val]++;
    frfr[fr[val]]++;
    if (fr[val] > result) {
        result = fr[val];
    }
}

void remValue(int val) {
    frfr[fr[val]]--;
    if (fr[val] == result && frfr[fr[val]] == 0) {
        result--;
    }
    fr[val]--;
    frfr[fr[val]]++;
}

void scanWindows() {
    int i;
    result = 0;
    fr.clear();
    for (i = 0; i < k; i++) {
        addValue(a[i]);
    }
    rez[0] = result;
    for (i = k; i < n; i++) {
        remValue(a[i - k]);
        addValue(a[i]);
        rez[i - k + 1] = result;
    }
    // stergem restul elementelor pentru ca frfr sa fie setat la 0 la final
    for (i = n; i < n + k; i++) {
        remValue(a[i - k]);
    }
}

void answerQueries() {
    int i, st, dr;
    for (i = 0; i < q; i++) {
        std::cin >> st >> dr;
        std::cout << k - rez[st - 1] << "\n";
    }
}

void solveTest() {
    readArray();
    scanWindows();
    answerQueries();
}

int main() {
    int t;
    fastReadWrite();
    std::cin >> t;
    while (t--) {
        solveTest();
    }
    return 0;
}

Versiunea grea

Noi trebuie, de fapt, să avem o subsecvență (contiguă) de exact kk elemente. Observăm că f(al,al+1,..,ar)=k−max(rezl,rezl+1,..,rezr−k+1)f(a_l, a_{l+1}, .., a_r) = k - max(rez_l, rez_{l+1}, .., rez_{r-k+1}) (încercăm fiecare subsecvență de kk elemente). Așa că, răspunsul nostru este ∑i=lr k−max(rezl,rezl+1,…,rezi−k+1)\sum _{i=l} ^r \ k - max(rez_l, rez_{l+1}, \dots, rez_{i-k+1}).

Vom găsi, pentru fiecare ii, la câte sume contribuie rezirez_i. Cu alte cuvinte, vom afla pentru câți j>ij > i avem max(rezl,rezl+1,…,rezj)=rezimax(rez_l, rez_{l+1}, \dots, rez_j) = rez_i. De asemenea, pentru a nu număra de mai multe ori anumite sume, vom presupune că nu există l≤p<il \leq p < i astfel încât rezp=rezirez_p = rez_i. Fie nxt0,i=nxt_{0, i} = cel mai mic j>ij > i astfel încât rezj>=rezirez_j >= rez_i, lucru pe care îl vom afla cu stivă. Fie sum0,i=rezi⋅(i−nxt0,i)sum_{0, i} = rez_i \cdot (i - nxt_{0, i}).

Acum, să presupunem că avem un arbore, în care nxt0,inxt_{0, i} reprezintă părintele lui ii și sum0,isum_{0, i} reprezintă costul muchiei de la ii la părintele lui ii. Noi vom pleca de la ll și vom tot merge în tatăl nodului, până când indicele tatălui este mai mare decât rr. Pentru a afla al câtelea tată este cu ușurinta, vom precalcula nxti,j=nxt_{i, j} = al 2i2^i-lea tată al lui jj și sumi,j=sum_{i, j} = suma costurilor muchiilor lanțului de la jj la cel de-al 2i2^i-lea tată al lui jj.

nxti,j=nxti−1,nxti−1,jsumi,j=sumi−1,j+sumi−1,nxti−1,jnxt_{i, j} = nxt_{i-1, nxt_{i-1, j}} \\ sum_{i, j} = sum_{i-1, j} + sum_{i-1, nxt_{i-1, j}}

Sursa de accepted:

#include <iostream>
#include <map>

const int MAXN = 200'000;
const int LOGN = 18;
const int INFINIT = 1'000'000'000;

int n, k, q, result, a[MAXN], rez[MAXN + 1], frfr[MAXN + 1], stiva[MAXN];
int nxt[LOGN][MAXN + 1];
long long sum[LOGN][MAXN + 1];
std::map<int, int> fr;

void fastReadWrite() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
}

void readArray() {
    int i;
    std::cin >> n >> k >> q;
    for (i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i] -= i;
    }
}

void addValue(int val) {
    frfr[fr[val]]--;
    fr[val]++;
    frfr[fr[val]]++;
    if (fr[val] > result) {
        result = fr[val];
    }
}

void remValue(int val) {
    frfr[fr[val]]--;
    if (fr[val] == result && frfr[fr[val]] == 0) {
        result--;
    }
    fr[val]--;
    frfr[fr[val]]++;
}

void scanWindows() {
    int i;
    result = 0;
    fr.clear();
    for (i = 0; i < k; i++) {
        addValue(a[i]);
    }
    rez[0] = result;
    for (i = k; i < n; i++) {
        remValue(a[i - k]);
        addValue(a[i]);
        rez[i - k + 1] = result;
    }
    // stergem restul elementelor pentru ca frfr sa fie setat la 0 la final
    for (i = n; i < n + k; i++) {
        remValue(a[i - k]);
    }
}

void buildTable() {
    int sp, i, j;
    n -= k - 1;
    stiva[0] = n;
    sp = 1;
    nxt[0][n] = n;
    sum[0][n] = 0;
    rez[n] = INFINIT;  // infinit
    for (i = n - 1; i >= 0; i--) {
        while (rez[i] > rez[stiva[sp - 1]]) {
            sp--;
        }
        nxt[0][i] = stiva[sp - 1];
        sum[0][i] = 1LL * rez[i] * (stiva[sp - 1] - i);
        stiva[sp++] = i;
    }

    for (i = 1; i < LOGN; i++) {
        for (j = 0; j <= n; j++) {
            nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
            sum[i][j] = sum[i - 1][j] + sum[i - 1][nxt[i - 1][j]];
        }
    }
}

void answerQueries() {
    int i, st, dr, j;
    long long ans = 0;
    for (i = 0; i < q; i++) {
        std::cin >> st >> dr;
        st--;
        dr -= k;
        ans = 1LL * k * (dr - st + 1);
        for (j = LOGN - 1; j >= 0; j--) {
            if (nxt[j][st] <= dr) {
                ans -= sum[j][st];
                st = nxt[j][st];
            }
        }
        ans -= 1LL * rez[st] * (dr - st + 1);
        std::cout << ans << "\n";
    }
}

void solveTest() {
    readArray();
    scanWindows();
    buildTable();
    answerQueries();
}

int main() {
    int t;
    fastReadWrite();
    std::cin >> t;
    while (t--) {
        solveTest();
    }
    return 0;
}

Observație

Această soluție este foarte asemănătoare cu soluția la problema strămoși, discutată în articolul de LCA

Concluzii

Sparse Table este una dintre structurile de date care răspunde la întrebări pe un interval într-un șir static. Chiar dacă arborii de intervale pot face aproape tot ce poate face și Sparse Table, de obicei cu o complexitate chiar mai bună, Sparse Table este mai ușor de implementat. De asemenea, am văzut că RMQ poate avea multe avantaje, dar și dezavantaje față de AINT.

Probleme suplimentare

Resurse suplimentare

Arbori indexați binar

Previous Page

Trie (arbore de prefixe)

Next Page

On this page

IntroducereSparse Table. Binary LiftingRange Minimum QueryRMQ 2DReverse RMQRMQ sau Arbori de intervale?Comparație în funcție de timpComparație în funcție de memorieAlte precizăriConcluzieProbleme rezolvateProblema excursieProblema Yunli's Subarray QueriesVersiunea ușoarăVersiunea greaConcluziiProbleme suplimentareResurse suplimentare