Frekventnost u opsegu

Napisati generičku klasu frekventnost_u_opsegu<T> koja implementira strukturu podataka koja podržava sledeće operacije:

void dodaj(const T& vrednost) - dodaje vrednost u strukturu podataka.
size_t frekventnost(const T& element, const size_t L, const size_t D) - vraća frekventnost elementa u opsegu indeksa [L, D].

Funkcija dodaj treba da radi u amortizovanoj vremenskoj složenosti $O(1)$, dok funkcija frekventnost treba da radi u vremenskoj složenosti $O(\log n)$, gde je n broj elemenata u strukturi podataka.

Ulaz

Sa standardnog ulaza, sve do kraja ulaza, učitavaju se naredbe u formatu:

a x - dodaje vrednost x (celo broj) u strukturu podataka.
f x L D - ispisuje frekventnost vrednosti x u opsegu indeksa [L, D].

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi f.

Primer

`stdin`

a 1
a 2
a 3
a 2
a 1
a 2
a 2
a 2
f 2 0 5

Izlaz

Rešenje

`main.cpp`

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

namespace matf
{
	/* Klasa za frekventnost u opsegu */
	template <typename T>
	class frekventnost_u_opsegu
	{
		public:
			/* Dodaje element u strukturu */
			void dodaj(const T& vrednost)
			{
				elementi.push_back(vrednost);
				lista_indeksa[vrednost].push_back(elementi.size() - 1);
			}

			/* Vraca frekventnost elemenata u opsegu [L, D] */
			size_t frekventnost(const T& element, const size_t L, const size_t D) const
			{
				auto it = lista_indeksa.find(element);
				if (it == lista_indeksa.end()) {
					return 0; // Element ne postoji
				}

				const auto& indeksi = it->second;

				// Pronalazenje donje granice
				auto donja_granica = std::lower_bound(indeksi.begin(), indeksi.end(), L);
				// Pronalazenje gornje granice
				auto gornja_granica = std::upper_bound(indeksi.begin(), indeksi.end(), D);

				return std::distance(donja_granica, gornja_granica);
			}

		
		private:
			std::vector<T> elementi;
			std::unordered_map<T, std::vector<size_t>> lista_indeksa;
	};
};

int main(void)
{
	matf::frekventnost_u_opsegu<int> fs;

	char op;

	while (std::cin >> op) {
		if (op == 'a') {
			int vrednost; std::cin >> vrednost;
			fs.dodaj(vrednost);
		} else if (op == 'f') {
			int element; size_t L, D;
			std::cin >> element >> L >> D;
			size_t freq = fs.frekventnost(element, L, D);
			std::cout << freq << std::endl;
		}
	}

	return 0;
}