Irrigation

Explicación

Podemos restar $n$ de cada consulta, ordenar las ciudades por ocurrencias y las consultas por año, y luego responder las consultas de forma offline.

Sea la ciudad $i$ la $i$ -ésima ciudad más pequeña ordenada por ocurrencias, y $occ_i$ el número de ocurrencias. Podemos recorrer cada $i$ y llevar los años que han pasado.

Supongamos que las ciudades $1, 2, \dots i$ ya tienen $occ_i$ ocurrencias. Para que todas terminen con $occ_{i+1}$ ocurrencias, necesitamos $i \cdot (occ_{i+1} - occ_i)$ años más, lo que significa que durante los próximos $i \cdot (occ_{i+1} - occ_i)$ años, las ciudades $1, 2, \dots i$ se seleccionarán una tras otra.

Para responder años individuales, podemos usar un BST para llevar los índices iniciales de cada ciudad $1, 2, 3 \dots i$ . Nótese que los índices iniciales, no los ordenados, desempatan las ocurrencias.

Sea el año actual $y$ . En cada iteración, podemos responder cada consulta $q$ en el rango $y \leq q < y + i \cdot (occ_{i+1} - occ_i)$ y usar búsqueda binaria para obtener los índices de estas consultas. Como estas ciudades se seleccionan una tras otra, la respuesta a la consulta $q$ es simplemente la $(q - y) \% i$ -ésima ciudad ordenada por índices iniciales.

En este punto, sabemos que cada ciudad tiene la ocurrencia máxima, así que la respuesta a las consultas restantes que piden años posteriores al $y$ final es simplemente $(q - y) \% m$ .

Implementación

Complejidad temporal: $\mathcal{O}(m \log q \log m)$

C++


#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
 
using ll = long long;
#define all(x) x.begin(), x.end()
 
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
int main() {
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	vector<int> counter(m);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		counter[--x]++;
	}
 
	vector<pair<ll, int>> query(q);  // {year, index}
	for (int i = 0; i < q; i++) {
		scanf("%lld", &query[i].first);
		query[i].first -= n;
		query[i].second = i;
	}
	sort(all(query));
 
	vector<pair<ll, int>> occ(m);  // {occurrence, city}
	for (int i = 0; i < m; i++) { occ[i] = {counter[i], i}; }
	sort(all(occ));
 
	vector<int> qans(q, -1);
	// tracks the initial indices of the cities so far in sorted order
	ordered_set<int> track_city;
 
	ll years = 1;
	for (int i = 0; i < m - 1; i++) {
		ll years_upper = years + (occ[i + 1].first - occ[i].first) * (i + 1);
		track_city.insert(occ[i].second);
 
		// beginning of query, sorted by year
		int q_low_ind = lower_bound(all(query), make_pair(years, 0)) - query.begin();
 
		for (int j = q_low_ind; j < q && query[j].first < years_upper; j++) {
			ll qyears = query[j].first;
			int qindex = query[j].second;
 
			// retrieve the requested city by original query order
			qans[qindex] = *track_city.find_by_order((qyears - years) % (i + 1));
		}
 
		years = years_upper;
	}
 
	// answer the rest of the queries that goes past max occurrence
	for (int i = 0; i < q; i++) {
		if (qans[query[i].second] == -1) {
			qans[query[i].second] = (query[i].first - years) % m;
		}
	}
 
	for (int i : qans) { printf("%d\n", i + 1); }
}