---
# System prepended metadata

title: Counting Islands (Hard)

---

# [Counting Islands (Hard)](https://po2punkt0.kattis.com/problems/raknaoarsvar)

# Subtask 1

This is an easier version of Counting Islands. The editorial can be found [here](https://typst.app/project/rSB2KmP3d2Zrfc61FLv88K).


## Subtask 3
Is is known that range mode query is believed to be difficult to solve in $O(N\log(N)^k)$ preprocessing and query time. See the Wikipedia page: [Range Mode Query](https://en.wikipedia.org/wiki/Range_mode_query#Results).

Our problem is of course slightly different: we have $l=1$ for all queries, but we have also have updates. Still, they are similar enough that we should probably look for a sqrt-based solution.

One reasonable candidate is [Mo's algorithm](https://cp-algorithms.com/data_structures/sqrt_decomposition.html#mos-algorithm). Conceptually, we create a 2D grid: along one axis, we have island sizes, and on the other we have "how many updates have we applied?". Thus, every point $(s,t)$ ($t$ means "time", if we imagine every update moving time forward by $1$) corresponds to having applied $t$ updates, and considered all islands with size $\geq s$. Every query corresponds to a point in this 2D grid. Our goal is thus to maintain a data structure that can answer queries, and then moving it to every query point. When we are at a query point, we ask for the answer to the query.

To make this easy for ourselves, let's create a sorted list of every island (size, country) that will appear throughout all updates. Initially, some will be disabled, because the updates to create them have not yet happened. When we apply updates, one island will be enabled, and another disabled.

With this, let's see how to do the Mo's. We will maintain a segment tree over countries: country $i$ stores the number of islands of country $i$ that are currently counted. This allows us to easily start counting / stop counting some island, and then extract the country with most islands in $O(\log(N))$. This works, but runs in ~$O((T+Q)\sqrt{Q}\log(N))$.

## Full solution
Let's use an assymetry of Mo's: we will perform $O((T+Q)\sqrt{Q})$ updates, but only $O(Q)$ queries. We thus want to find a data structure that allows us to:
- Update $a[i]$ in ~$O(1)$
- Query for the largest element in ~$O(\sqrt{N})$

If this was possible, the time complexity would change to $O((T+Q)\sqrt{Q}+Q\sqrt{N})$, which is definitely fast enough. Unfortunately, as far as I'm aware, such a data structure cannot exist.

Instead, we can imagine keeping a large boolean array over which values $N \cdot$ islands counted + island index. The index of the largest one in this array is our answer, and we can update it in $O(1)$. Unfortunately, querying it takes $O(\frac{NT}{64})$. To reduce it, we can use the fact that there can only $O(\sqrt{T})$ unique amounts of islands that countries have at any time. Thus, we store a bitset of size $N$ for each such quantity. By careful book-keeping, updates can still be done in $O(1)$, and queries take $O(\sqrt{T}+\frac{N}{64})$.

In total, we get $O((T+Q)\sqrt{Q}+Q(\sqrt{T}+\frac{N}{64}))$. The runtime is dominated by the updates, not the queries.

Other non-Mo solutions also exist.