Balkan OI 2015 - Happiness

Isn't it convenient how the problem statement tells us what we have to do? (Try to prove the necessary condition described in the statement yourself.)

We need a data structure that supports the following:

• Insert numbers into a multiset $M$.
• Erase numbers from $M$.
• Check whether there exists some number $x < \sum_{i \in M} i$ such that $\sum_{i \in M, i \leq x}i < x$.

Solution 1 - Sparse Segment Tree

Since we want to handle range queries with updates, the obvious option would be to use a BIT or segment tree.

However, the numbers that we want to insert can get very large (up to $10^{12}$). Since we have to answer queries online, using a BIT is out of the question.

Luckily, we can simply use a sparse segment tree instead!

We still need to find a way to check whether the $x$ described above exists though.

The key observation is that if we know that

for some $k$, then we also know that

for all $l \in (k, \sum_{i \in M, i \leq k}i]$. This is true because

This means that the next number we need to check is $\sum_{i \in M, i \leq k}i + 1$.

If we choose the numbers that we check this way, then we will only check $\mathcal{O}(\log 10^{12})$ numbers for each query (since the $i$-th number we check is always at least $2^i - 1$).

The complexity of this algorithm is thus $\mathcal{O}(KQ \log^2 10^{12})$.

Code

Copy
#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) {

Solution 2 - Buckets

A smarter solution is to split the elements of $M$ into the buckets $[2^i, 2^{i + 1})$ for each $i$ from 0 to $\log 10^{12}$. Notice how there are exactly $\log 10^{12} + 1$ buckets.

Why is this convenient?

Firstly, only the two least elements in each bucket could potentially be bad (since $(2^k + a) + (2^k + b) \geq 2^{k + 1}$). This narrows down the number of elements we need to check significantly.

Secondly, we can store the sum of the elements in each bucket and be able to find the prefix sums of buckets in $\mathcal{O}(\log 10^{12})$ time.

We can use multisets to store the elements in the buckets, so the complexity of this algorithm is $\mathcal{O}(KQ (\log 10^{12} + \log KQ))$. In practice, this solution runs faster than the first solution.

Code

Copy
#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) {