Sjeltzer?

Editorial oficial (C++) 

Explicación

El ID de cada bebida es un string de 6 dígitos. Tratamos cada posición de dígito como su propio eje con valores $0$–$9$. Entonces cada bebida es un único punto en una grilla de 6 dimensiones, y una consulta pide el tamaño total sobre una caja de 6 dimensiones: un intervalo $[x_k, y_k]$ por eje. Esto es exactamente lo que maneja una suma de prefijos, solo que en seis dimensiones en lugar de dos.

Construir la suma de prefijos 6D

El arreglo ps[11][11][11][11][11][11] es el arreglo de sumas de prefijos. Cada tamaño se registra como ps[d0+1][d1+1]…[d5+1] = size para no tener que hacer análisis por casos al restar con indexación desde cero durante las consultas.

Luego precompute() lo convierte en una suma de prefijos. En 2D se barre a la derecha y después hacia abajo; aquí se barre una vez a lo largo de cada una de las 6 dimensiones. El código lo hace de forma compacta: para cada dimensión i, visita cada celda, retrocede un índice a lo largo del eje i (tr[i]--) y suma el valor de esa celda vecina. Tras los seis barridos, ps[a1][a2]…[a6] guarda el tamaño total de toda bebida cuyo $k$-ésimo dígito cumple $s_k \le a_k - 1$ para todo $k$.

Responder una consulta con inclusión-exclusión

Una consulta da dos strings de cotas s1 (inferior) y s2 (superior), es decir, un rango $[x_k, y_k]$ por eje. Sumar sobre una caja a partir de un arreglo de sumas de prefijos es el truco de inclusión-exclusión, generalizado:

• un rango 1D $[x, y]$ es ps(y) − ps(x − 1);
• una caja 2D es ps(y0,y1) − ps(x0−1,y1) − ps(y0,x1−1) + ps(x0−1,x1−1).

Para 6 ejes hay $2^6 = 64$ esquinas. El código itera una máscara de 6 bits; para cada eje elige o bien el extremo superior $y_k$ (índice $y_k + 1$, empujado a query_pos y contado por cnt) o la posición justo debajo del extremo inferior (índice $x_k$, que representa "$\le x_k - 1$"). Luego lee ps en esa esquina y la suma o resta, restando cuando cnt es impar; de forma equivalente, cuando un número impar de ejes usa el extremo inferior (ambos tienen la misma paridad porque hay 6 ejes). Importa un caso más: si algún eje tiene $x_k > y_k$, entonces ningún dígito puede ser a la vez $\ge x_k$ y $\le y_k$ en ese eje, así que la caja de la consulta no contiene bebidas y la respuesta es $0$. El código lo comprueba primero y corta el cálculo, porque inclusión-exclusión asume cotas válidas.

Implementación

Complejidad temporal: $\mathcal{O}(10^6 + Q)$

#include <bits/stdc++.h>
using namespace std;
 
const int D = 11;                // 10 valores de dígito (0-9) + 1 para sumas de prefijos indexadas desde uno
long long ps[D][D][D][D][D][D];  // arreglo de sumas de prefijos
 
void precompute() {
	for (int i = 0; i < 6; i++) {  // propagamos el valor en cada una de las 6 dimensiones
		for (int i1 = 1; i1 <= 10; i1++) {
			for (int i2 = 1; i2 <= 10; i2++) {
				for (int i3 = 1; i3 <= 10; i3++) {
					for (int i4 = 1; i4 <= 10; i4++) {
						for (int i5 = 1; i5 <= 10; i5++) {
							for (int i6 = 1; i6 <= 10; i6++) {
								vector<int> tr = {i1, i2, i3, i4, i5, i6};
								tr[i]--;
								ps[i1][i2][i3][i4][i5][i6] +=
								    ps[tr[0]][tr[1]][tr[2]][tr[3]][tr[4]][tr[5]];
							}
						}
					}
				}
			}
		}
	}
}
 
int main() {
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		vector<int> ind;
		long long x;
		cin >> x;
		for (auto j : s) ind.push_back(j - '0' + 1);
		ps[ind[0]][ind[1]][ind[2]][ind[3]][ind[4]][ind[5]] = x;
	}
 
	precompute();
 
	int q;
	cin >> q;
	while (q--) {
		string s1, s2;
		cin >> s1 >> s2;
		int f = 0;
		for (int j = 0; j < 6; j++) {
			if (s1[j] > s2[j]) {  // la cota inferior supera a la superior en este eje ->
				                  // caja vacía -> 0
				f = 1;
				cout << 0 << "\n";
				break;
			}
		}
		if (f) continue;
		long long ans = 0;
		for (int i = 0; i < 64; i++) {
			vector<int> query_pos;
			int cnt = 0;
			for (int j = 0; j < 6; j++) {
				if (i & (1 << j)) {
					query_pos.push_back(s2[j] - '0' + 1);
					cnt++;
				} else query_pos.push_back(s1[j] - '0');
			}
			if (cnt & 1)
				ans -= ps[query_pos[0]][query_pos[1]][query_pos[2]][query_pos[3]]
				         [query_pos[4]]
				         [query_pos[5]];  // cantidad impar de "-1", restamos el valor
			else
				ans += ps[query_pos[0]][query_pos[1]][query_pos[2]][query_pos[3]]
				         [query_pos[4]][query_pos[5]];
		}
		cout << ans << "\n";
	}
	return 0;
}