Skip to Content
CTRL K

Distinct Values Queries

Pista

Ordenar las consultas en un orden específico antes de responderlas.

Solución

Explicación

Respondemos las consultas de derecha a izquierda, ordenadas por sus índices izquierdos. Usando un Árbol de Fenwick (BIT), podemos llevar la cuenta de los índices que contienen valores distintos. Para cada valor arr[i]arr[i], ponemos el índice más reciente (es decir, el más a la izquierda) en bit[i]bit[i] a 11. Si este valor apareció antes, ponemos el último índice usado de vuelta a 00. Luego, podemos responder todas las consultas con a=ia = i sumando los valores entre [i,b][i, b]. Esto garantiza que los índices posteriores a ii estén incluidos en el BIT para responder las consultas con precisión.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N\log{N})

#include <bits/stdc++.h>
using namespace std;
 
// BeginCodeSnip{BIT}
struct BIT {
	int size;
	vector<int> bit;
	BIT(int n) : size(n), bit(n + 1) {}
	void update(int x, int v) {
		x++;
		for (; x <= size; x += x & (-x)) { bit[x] += v; }
	}
	/** @return suma de los valores en [0,b] */
	int query(int b) {
		b++;
		int result = 0;
		for (; b > 0; b -= b & (-b)) { result += bit[b]; }
		return result;
	}
};
// EndCodeSnip
 
int main() {
	int n, q;
	cin >> n >> q;
 
	vector<int> arr(n);
	vector<vector<pair<int, int>>> queries(n);
	for (int i = 0; i < n; i++) { cin >> arr[i]; }
	for (int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		queries[a].push_back({b, i});
	}
 
	BIT bit(n);
	// last_index[val] es el índice más a la izquierda donde arr[last_index[val]] = val.
	map<int, int> last_index;
	vector<int> solution(q, -1);
	// Actualizar los índices y responder las consultas de derecha a izquierda.
	for (int i = n - 1; i >= 0; i--) {
		int val = arr[i];
		/*
		 * Si val ya apareció antes, entonces el valor guardado ya no
		 * es el índice más a la izquierda, así que lo borramos del BIT.
		 */
		if (last_index.count(val) > 0) bit.update(last_index[val], -1);
		// i se convierte en el índice más a la izquierda.
		last_index[val] = i;
		bit.update(i, 1);
 
		// Responder todas las consultas con a == i.
		for (auto &qr : queries[i]) {
			/*
			 * La solución de esta consulta es bit[i,b].
			 * Esto es igual a bit[0,b] porque bit[0,i-1] = 0.
			 */
			solution[qr.second] = bit.query(qr.first);
		}
	}
 
	for (auto &a : solution) { cout << a << "\n"; }
}
import java.io.*;
import java.util.*;
 
public class DistinctValuesQueries {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
 
		int[] arr = new int[n];
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); }
 
		List<List<Pair>> queries = new ArrayList<>();
		for (int i = 0; i < n; i++) { queries.add(new ArrayList<>()); }
		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			a--;
			b--;
			queries.get(a).add(new Pair(b, i));
		}
		bf.close();
 
		// last_index[val] es el índice más a la izquierda donde arr[last_index[val]] =
		// val.
		Map<Integer, Integer> last_index = new HashMap<>();
		BIT bit = new BIT(n);
		int[] solution = new int[q];
		for (int i = n - 1; i >= 0; i--) {
			int val = arr[i];
			/*
			 * Si val ya apareció antes, entonces el valor guardado ya no
			 * es el índice más a la izquierda, así que lo borramos del BIT.
			 */
			if (last_index.containsKey(val)) { bit.update(last_index.get(val), -1); }
			// i se convierte en el índice más a la izquierda.
			last_index.put(val, i);
			bit.update(i, 1);
 
			// Responder todas las consultas con a == i.
			for (Pair qr : queries.get(i)) {
				/*
				 * La solución de esta consulta es bit[i,b].
				 * Esto es igual a bit[0,b] porque bit[0,i-1] = 0.
				 */
				solution[qr.second] = bit.query(qr.first);
			}
		}
 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i = 0; i < q; i++) {
			bw.write(Integer.toString(solution[i]));
			bw.write("\n");
		}
		bw.flush();
		bw.close();
	}
 
	// BeginCodeSnip{BIT}
	private static class BIT {
		int size;
		int[] bit;
 
		BIT(int n) {
			size = n;
			bit = new int[n + 1];
		}
 
		void update(int x, int v) {
			x++;
			for (; x <= size; x += x & -x) { bit[x] += v; }
		}
 
		/** @return suma de los valores en [0,b] */
		int query(int b) {
			b++;
			int result = 0;
			for (; b > 0; b -= b & -b) { result += bit[b]; }
			return result;
		}
	}
	// EndCodeSnip
 
	// BeginCodeSnip{Pair}
	private static class Pair {
		public int first;
		public int second;
 
		Pair(int a, int b) {
			first = a;
			second = b;
		}
	}
	// EndCodeSnip
}
Fundamentos