# PBinfo #3085 – fsecv – Rezolvare C++

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

## Enunț

Se consideră un șir A format din N numere întregi, numerotate de la 1 la N. Numim secvență a șirului A orice succesiune de elemente consecutive din șir de forma A[i], A[i+1], …, A[j], cu 0 < i < j ≤ N.

Cerința
Fiind dat șirul A cu N numere întregi se cere să se răspundă la Q întrebări de forma: i j k (0 < i < j ≤ N). Pentru fiecare întrebare se cere să se determine câte numere din secvența A[i], …, A[j] au frecvența de apariții egală cu k.

Date de intrare
Fișierul de intrare fsecv.in conține pe prima linie numerele naturale nenule N și Q cu semnificația din enunț. Pe următoarea linie se găsesc N numere întregi ce reprezintă valorile șirului A. Pe următoarele linii se află descrierea celor Q întrebări, câte una pe linie, în formatul precizat i j k.

Date de ieșire
Fișierul de ieșire fsecv.out va conține Q linii. Pe fiecare linie se va găsi răspunsul întrebării i, cu 1 ≤ i ≤ Q.

Restricții și precizări

2 < N ≤ 100.000
1 < Q ≤ 100.000
0 < k ≤ N
-100.000 ≤ A[i] ≤ 100.000; 1 ≤ i ≤ N

Exemplu:
fsecv.in

11 3
1 2 4 3 2 5 6 4 5 2 1
1 6 2
2 7 3
4 11 1
fsecv.out

1
0
4
Explicație
Secvența la care se referă prima întrebare este 1,2,4,3,2,5, iar răspunsul este egal cu 1.
Secvența la care se referă a doua întrebare este 2,4,3,2,5,6, iar răspunsul este egal cu 0.
Secvența la care se referă a treia întrebare este 3,2,5,6,4,5,2,1, iar răspunsul este egal cu 4.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
ifstream f("fsecv.in");
ofstream g("fsecv.out");
const int NM = 100003;
int n, block, q;
struct query{
    int l, r, k, p;
    bool operator < (const query &aux)const{
        if(l / block != aux.l / block) return l / block < aux.l / block;
        return r < aux.r;
    }
} Q[NM];
int a[NM], nr[NM], ap[2*NM], sol[NM];
void add(int i)
{
    int x = a[i] + 100000;
    if(ap[x] > 0) --nr[ap[x]];
    ++ap[x];
    ++nr[ap[x]];
}
void scoate(int i)
{
    int x = a[i]  + 100000;
    if(ap[x] > 0) --nr[ap[x]];
    --ap[x];
    ++nr[ap[x]];
}
int main()
{
    f >> n >> q;
    for(int i = 1; i <= n; ++i)
        f >> a[i];
    for(int i = 1; i <= q; ++i){
        f >> Q[i].l >> Q[i].r >> Q[i].k;
        Q[i].p = i;
    }
    block = sqrt(n);
    sort(Q + 1, Q + q + 1);
    int st = 1, dr = 0;
    for(int i = 1; i <= q; ++i){
        while(st > Q[i].l) --st, add(st);
        while(dr < Q[i].r) ++dr, add(dr);
        while(st < Q[i].l) scoate(st), ++st;
        while(dr > Q[i].r) scoate(dr), --dr;
        sol[Q[i].p] = nr[Q[i].k];
    }
    for(int i = 1; i <= q; ++i)
        g << sol[i] << '\n';
    return 0;
}
```

## Resurse

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