Skip to Content
CTRL K

Happiness

¿No es conveniente cómo el enunciado nos dice qué tenemos que hacer? (Intentemos demostrar por nuestra cuenta la condición necesaria descrita en el enunciado.)

Necesitamos una estructura de datos que soporte lo siguiente:

  • Insertar números en un multiconjunto MM.
  • Borrar números de MM.
  • Comprobar si existe algún número x<∑i∈Mix < \sum_{i \in M} i tal que ∑i∈M,i≤xi<x\sum_{i \in M, i \leq x}i < x.

Solución 1 - Árbol de Segmentos disperso

Como queremos manejar consultas de rango con actualizaciones, la opción obvia sería usar un BIT o un árbol de segmentos.

Sin embargo, los números que queremos insertar pueden ser muy grandes (hasta 101210^{12}). Como hay que responder las consultas online, usar un BIT queda descartado.

Por suerte, ¡podemos usar un árbol de segmentos disperso en su lugar!

Aun así necesitamos hallar una forma de comprobar si existe el xx descrito arriba.

La observación clave es que si sabemos que

k≤∑i∈M,i≤ki k \leq \sum_{i \in M, i \leq k}i

para algún kk, entonces también sabemos que

l≤∑i∈M,i≤li l \leq \sum_{i \in M, i \leq l}i

para todo l∈(k,∑i∈M,i≤ki]l \in (k, \sum_{i \in M, i \leq k}i]. Esto es cierto porque

l≤∑i∈M,i≤ki≤∑i∈M,i≤li l \leq \sum_{i \in M, i \leq k}i \leq \sum_{i \in M, i \leq l}i

Esto significa que el siguiente número que hay que revisar es ∑i∈M,i≤ki+1\sum_{i \in M, i \leq k}i + 1.

Si elegimos de esta forma los números que revisamos, entonces solo revisaremos O(log⁡1012)\mathcal{O}(\log 10^{12}) números por cada consulta (ya que el ii-ésimo número que revisamos es siempre al menos 2i−12^i - 1).

La complejidad de este algoritmo es entonces O(KQlog⁡21012)\mathcal{O}(KQ \log^2 10^{12}).

Código

#include "happiness.h"
 
struct Node {
	long long l, r, val;
	Node *lc, *rc;
 
	Node(long long L, long long R) : l(L), r(R), val(0), lc(nullptr), rc(nullptr) {}
 
	void update(long long p, long long v) {
		val += v;
		if (l != r) {
			long long mid = (l + r) / 2;
			if (p > mid) {
				if (!rc) rc = new Node(mid + 1, r);
				rc->update(p, v);
			} else {
				if (!lc) lc = new Node(l, mid);
				lc->update(p, v);
			}
		}
	}
 
	long long query(long long a, long long b) {
		if (r < a || l > b) return 0;
		if (r <= b && l >= a) return val;
		long long ret = 0;
		if (lc) ret += lc->query(a, b);
		if (rc) ret += rc->query(a, b);
		return ret;
	}
};
 
Node *root;
 
bool check() {
	long long curr = 1, sm = root->val;
	while (curr < sm) {
		long long t = root->query(1, curr);
		if (t < curr) return false;
		curr = t + 1;
	}
	return true;
}
 
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	root = new Node(1, maxCoinSize);
	for (int i = 0; i < coinsCount; i++) root->update(coins[i], coins[i]);
	return check();
}
 
bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i = 0; i < coinsCount; i++) root->update(coins[i], event * coins[i]);
	return check();
}

Solución 2 - Cubetas

Una solución más inteligente es partir los elementos de MM en las cubetas [2i,2i+1)[2^i, 2^{i + 1}) para cada ii de 0 a log⁡1012\log 10^{12}. Nótese que hay exactamente log⁡1012+1\log 10^{12} + 1 cubetas.

¿Por qué es esto conveniente?

En primer lugar, solo los dos elementos más pequeños de cada cubeta podrían ser malos (ya que (2k+a)+(2k+b)≥2k+1(2^k + a) + (2^k + b) \geq 2^{k + 1}). Esto reduce de forma significativa la cantidad de elementos que hay que revisar.

En segundo lugar, podemos guardar la suma de los elementos de cada cubeta y ser capaces de hallar las sumas de prefijos de las cubetas en tiempo O(log⁡1012)\mathcal{O}(\log 10^{12}).

Podemos usar multiconjuntos para guardar los elementos de las cubetas, así que la complejidad de este algoritmo es O(KQ(log⁡1012+log⁡KQ))\mathcal{O}(KQ (\log 10^{12} + \log KQ)). En la práctica, esta solución corre más rápido que la primera.

Código

#include "happiness.h"
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
multiset<ll> todo[40];
ll SUM[40];
 
void ad(ll x, int b) {
	int p = 0;
	while ((1LL << (p + 1)) <= x) p++;
	if (b == 1) {
		todo[p].insert(x), SUM[p] += x;
	} else {
		todo[p].erase(todo[p].find(x)), SUM[p] -= x;
	}
}
 
bool ok() {
	ll sum = 0;
	for (int i = 0; i < 40; ++i)
		if (todo[i].size() > 0) {
			ll x = *begin(todo[i]);
			if (sum + 1 < x) return 0;
			if (todo[i].size() > 1 && sum + x + 1 < *next(begin(todo[i]))) return 0;
			sum += SUM[i];
		}
	return 1;
}
 
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	for (int i = 0; i < coinsCount; ++i) ad(coins[i], 1);
	return ok();
}
 
bool is_happy(int event, int coinsCount, long long coins[]) {
	for (int i = 0; i < coinsCount; ++i) {
		if (event == -1) ad(coins[i], -1);
		else ad(coins[i], 1);
	}
	return ok();
}
Fundamentos