# PBinfo #3860 – consecutive1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Se dă un șir (a[1], a[2], ..., a[n]) de numere naturale cuprinse între 1 și n. Se dau de asemenea Q interogări, fiecare prin două numere x, y: dacă s-ar ordona a[x], a[x+1], ..., a[y], se obține sau nu o secvență de numere consecutive? (De exemplu, 5,3,6,4 dacă e ordonată se obține 3,4,5,6, care este o secvență de numere consecutive).

Cerința
Dându-se Q întrebări, să se răspundă la acestea. La fiecare interogare, dacă prin sortare se obține o secvență de numere consecutive veți afișa valoarea 1, iar în caz contrar veți afișa valoarea 0.

Date de intrare
De la tastatură, de pe prima linie se citește numărul natural n. Pe linia a doua se află n numere naturale reprezentând elementele șirului. Pe a treia linie se află numărul Q, iar pe următoarele Q linii se găsesc câte două numere naturale x și y, 1 ≤ x ≤ y ≤ n, reprezentând câte o interogare.

Date de ieșire
La ecran se vor afișa pe o singură linie, fără spații, Q cifre din mulțimea {0, 1} reprezentând răspunsurile la fiecare întrebare.

Restricții și precizări

Pentru 10 puncte, 3 ≤ n ≤ 50, 1 ≤ Q ≤ 100
Pentru 30 puncte, n ≤ 300, Q ≤ 10.000
Pentru 60 puncte, 10.000 ≤ n ≤ 100.000, Q ≤ 200.000

Exemplu:
Intrare

9
4 1 3 4 2 1 6 5 4
5
1 4
3 5
3 6
5 9
7 9
Ieșire

01101
Explicație
Sunt 5 interogări. 
Întrebarea 1: 4 1 3 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 2: 3 4 2 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 3: 3 4 2 1 obține o secvență de numere consecutive, deci răspunsul este 1.
Întrebarea 4: 2 1 6 5 4 nu obține o secvență de numere consecutive, deci răspunsul este 0.
Întrebarea 5: 6 5 4 obține o secvență de numere consecutive, deci răspunsul este 1.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
#define nmax 100001
using namespace std;
int n, a[nmax], rmin[18][nmax], rmax[18][nmax];
int P[nmax]; /// P[i] = j : secventa de la j la i are doar
             ///            numere distincte
int fr[nmax], lg[nmax];
void Citire()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
}
void ConstructieP()
{
    int i, j, x;
    j = 1;
    for (i = 1; i <= n; i++)
    {
        x = a[i];
        while (fr[x] != 0)
        {
            fr[a[j]]--;
            j++;
        }
        fr[x]++;
        P[i] = j;
    }
}
void RMQ()
{
    int i, j, k;
    /// lg[i] = k - exponentul maxim cu proprietatea
    /// ca 2^k este mai mic sau egal cu i
    lg[1] = 0;
    for (i = 2; i <= n; i++)
        lg[i] = lg[i / 2] + 1;
    /// ---------------- rmin ------------------------
    for (i = 1; i <= n; i++)
        rmin[0][i] = a[i];
    for (i = 1; (1 << i) <= n; i++)
        for (j = (1 << i); j <= n; j++)
        {
            k = 1 << (i - 1);
            rmin[i][j] = min(rmin[i - 1][j], rmin[i - 1][j - k]);
        }
    /// ---------------- rmax ------------------------
    for (i = 1; i <= n; i++)
        rmax[0][i] = a[i];
    for (i = 1; (1 << i) <= n; i++)
        for (j = (1 << i); j <= n; j++)
        {
            k = 1 << (i - 1);
            rmax[i][j] = max(rmax[i - 1][j], rmax[i - 1][j - k]);
        }
}
void Interogari()
{
    int Q, x, y, k, m, M;
    cin >> Q;
    while (Q--)
    {
        cin >> x >> y;
        if (P[y] <= x) /// secventa a[x..y] are doar nr. distincte
        {
            k=lg[y - x + 1];
            m = min(rmin[k][x + (1<<k) - 1], rmin[k][y]);
            M = max(rmax[k][x + (1<<k) - 1], rmax[k][y]);
            if (M - m == y - x) cout << "1";
            else cout << "0";
        }
        else cout << "0";
    }
}
int main()
{
    Citire();
    ConstructieP();
    RMQ();
    Interogari();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3860)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3860/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3860/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)