# PBinfo #3108 – dss – Rezolvare C++

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

## Enunț

Se dau N numere naturale s[1], s[2], …, s[N] și Q interogări de forma a b.

Cerința
Să se determine pentru fiecare interogare [a;b] numărul de subșiruri formate din elemente distincte ale secvenței s[a], s[a+1], s[a+2], …, s[b]. 
Prin secvență a șirului s se înțelege orice succesiune de elemente aflate pe poziții consecutive s[a], s[a+1], …, s[b], cu 1 ≤ a ≤ b ≤ N.
Prin subșir al șirului s se înțelege orice succesiune de elemente aflate pe poziții în ordine strict crescătoare, dar nu neapărat consecutive, sa1, sa2, …, sak cu  1 ≤ a1 < a2 < ... < ak ≤ N.

Date de intrare
Fișierul de intrare dss.in conține pe primul rând numerele N și Q. Pe linia a doua sunt scrise N numere naturale separate prin câte un spațiu. Pe următoarele Q rânduri sunt scrise câte două numere naturale a b@, separate prin spațiu, reprezentând capetele intervalelor de interogare date.

Date de ieșire
În fișierul de ieșire dss.out pe fiecare dintre primele Q rânduri este scris câte un număr natural reprezentând numărul tuturor subșirurilor formate din elemente distincte conținute în secvența din  interogarea corespunzătoare.

Restricții și precizări

1 ≤ N ≤ 400.000
1 ≤ Q ≤ 10.000
1 ≤ s[k] ≤ N
1 ≤ a ≤ b ≤ N
Numărul de subșiruri pentru fiecare interogare vor fi calculate modulo 1.000.000.007

Exemplu:
dss.in

5 3 
1 2 3 2 3
1 4
2 5
1 3
dss.out

11
8
7
Explicație
- Subșirurile formate din elemente distincte din secvența s[1..4]=(1 2 3 2) sunt 1, 2, 3, 2, 1 2, 1 3, 1 2, 2 3, 3 2, 1 2 3, 1 3 2, deci în total 11 subșiruri. 
- Subșirurile formate din elemente distincte din secvența s[2..5]=(2 3 2 3) sunt 2, 3, 2, 3, 2 3, 2 3, 3 2, 2 3, deci 8 subșiruri. 
- Subșirurile formate din elemente distincte din secvența s[1..3]=(1 2 3) sunt 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3, deci 7 subșiruri.

## Cod sursă C++

```cpp
// O(N * sqrt(Q))
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_N   500001
#define MAX_Q   10001
#define MOD     1000000007
typedef struct {
    int a, b, bidx, qidx;
} QUERY;
int     x[MAX_N], f[MAX_N], inv[MAX_N], ans[MAX_Q];
QUERY   q[MAX_Q];
int cmp(const void *u, const void *v) {
    QUERY *p = (QUERY *)u, *q = (QUERY *)v;
    return (p->bidx != q->bidx) ? (p->bidx - q->bidx) : (p->b - q->b);
}
void add(int v, int *f, int *inv, int *p) {
    *p = 1LL * (*p) * inv[f[v]] % MOD * (f[v] + 1) % MOD;
    f[v]++;
}
void rem(int v, int *f, int *inv, int *p) {
    *p = 1LL * (*p) * inv[f[v]] % MOD * (f[v] - 1) % MOD;
    f[v]--;
}
int main() {
    FILE    *fin  = fopen("dss.in",  "r");
    FILE    *fout = fopen("dss.out", "w");
    int     n, nq, BLOCK;
    fscanf(fin, "%d %d", &n, &nq);
    BLOCK = n / sqrt(nq);
    for (int i = 0; i < n; i++) fscanf(fin, "%d", x + i);
    for (int i = 0; i < nq; i++) {
        fscanf(fin, "%d %d", &q[i].a, &q[i].b);
        q[i].a--; q[i].b--; q[i].qidx = i; q[i].bidx = q[i].a/BLOCK;
    }
    inv[1] = 1;
    for (int i = 2; i <= n; i++) {
        inv[i] = 1LL * (MOD - MOD/i) * inv[MOD % i] % MOD;
    }
    qsort(q, nq, sizeof(QUERY), cmp);
    for (int i = 0; i < MAX_N; i++) f[i] = 1;
    int a = 0, b = 0, p = 2; f[x[0]]++;
    for (int i = 0; i < nq; i++) {
        while (b < q[i].b) add(x[++b], f, inv, &p);
        while (b > q[i].b) rem(x[b--], f, inv, &p);
        while (a > q[i].a) add(x[--a], f, inv, &p);
        while (a < q[i].a) rem(x[a++], f, inv, &p);
        ans[q[i].qidx] = p - 1;
    }
    for (int i = 0; i < nq; i++) fprintf(fout, "%d\n", ans[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}
```

## Resurse

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