# PBinfo #3712 – median_query – Rezolvare C++

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

## Enunț

Cerința
Se dau un șir de N numere naturale nenule indexat de la 1 și Q query-uri de forma l r. Să se afișeze pentru fiecare query l r medianul secvenței l r din șir.

Date de intrare
Fișierul de intrare median_query.in conține pe prima linie numerele N și Q, iar pe a doua linie N numere naturale nenule separate prin spații. Pe următoarele Q linii se va afla câte o pereche de numere l r reprezentând query-urile.

Date de ieșire
Fișierul de ieșire median_query.out va conține răspunsurile la cele Q query-uri, câte unul pe fiecare linie.

Restricții și precizări

1 ≤ N, Q ≤ 100.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
1 ≤ l ≤ r ≤ N
medianul unei secvențe l r este valoarea care s-ar afla pe poziția [(r - l + 2) / 2] în secvența l r dacă aceasta ar fi sortată crescător, unde [x] = partea întreagă a numărului x.

Exemplu:
median_query.in

7 4
1 3 2 5 10 2 3
1 3
4 6
1 7
2 5
median_query.out

2
5
3
3
Explicație
Secvența 1 3 sortată crescător este: 1 2 3. Medianul acesteia este 2.

Secvența 4 6 sortată crescător este: 2 5 10. Medianul acesteia este 5.

Secvența 1 7 sortată crescător este: 1 2 2 3 3 5 10. Medianul acesteia este 3.

Secvența 2 5 sortată crescător este: 2 3 5 10. Medianul acesteia este 3.

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
// Solutia "brute-force" - Lorintz Alexandru
// 40 de puncte
// Complexitate: O(Q * N * log(N))
using namespace std;
ifstream fin("median_query.in");
ofstream fout("median_query.out");
int main() {
    int N, Q;
    fin >> N >> Q;
    vector<int> a(N + 1);
    for(int i = 1; i <= N; ++i)
        fin >> a[i];
    while(Q--) {
        int l, r;
        fin >> l >> r;
        vector<int> v{0};
        for(int i = l; i <= r; ++i)
            v.emplace_back(a[i]);
        sort(v.begin() + 1, v.end());
        fout << v[(r - l + 2) >> 1] << '\n';
    }
}
```

## Resurse

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