CSES - Jättimäinen RMQ
  • Time limit: 3.00 s
  • Memory limit: 512 MB
Olkoon $A$ taulukko. Tehtävänäsi on vastata kyselyihin, missä annettuna $L$ ja $R$, sinun pitää palauttaa pienin arvo $A[ i ]$ kaikkien $L \leq i \leq R$ yli.


Syöte

Koska syöte on niin iso, se annetaan satunnaisgeneraattorin muodossa. Syötteen muodostaa seuraava koodi:
uint64_t next(uint64_t& x) {
    uint64_t z = (x += 0x9e3779b97f4a7c15);
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
}

const int N = 1e7;
const int Q = 1e7;
int A[N];
int L[Q];
int R[Q];

void genInput(int n, int q, int h, uint64_t x) {
    for (int i = 0; i < n; ++i) A[i] = next(x) % h;

    for (int i = 0; i < q; ++i) {
        L[i] = next(x) % n;
        R[i] = next(x) % n;
        if (L[i] > R[i]) swap(L[i], R[i]);
    }
}
Ensimmäinen rivi syötettä sisältää neljä lukua $n$, $q$, $h$ ja $x$: taulukon koko, kyselyiden määrä, suurin mahdollinen taulukon arvo ja satunnaisgeneraattorin seedi. Anna nämä arvot genInput-funktiolle.

Kyselyn $j$, $0 \leq j < q$ vastaus on pienin arvo $A[ i ]$, kaikkien $L[ j ] \leq i \leq R[ j ]$ yli. Taulukko $A$ on nolla-indeksoitu.

Tuloste

Tulosta yksi luku: kyselyiden vastausten summa.

Rajat
  • $1 \leq n \leq 10^7$
  • $1 \leq q \leq 10^7$
  • $1 \leq h \leq 10^9$
Esimerkki

Syöte:
12 5 10 101

Tuloste:
5

Tällä syötteellä A = [1 1 2 5 9 3 9 7 0 0 3 7], ja kyselyt koskevat intervalleja [1, 7], [4, 10], [3, 10], [1, 5] ja [4, 7]. Vastaukset näihin kyselyihin ovat 1, 0, 0, 1 ja 3.