Describe a data structure to track visitors
The idea is to keep a sorted list of non-empty &quot;buckets&quot;. Each bucket $v$ is associated to a certain number $n_v$ of people that wish to visit some city and contains all the cities $c$ that wish to be visited by exactly $n_v$ people.
By keeping a suitable set of pointers cities can be moved from one bucket to the next in constant time. To perform a Favorite($k$) operation it suffices to look at the &quot;last&quot; buckets in the sorted list.

The data structure consists of:

A doubly-linked list $L$. Each node $v$ of $L$ is associated to an integer $\eta_v$ and to a (pointer) to an inner list $\ell_v$ of cities $c$ such that exactly $\eta_v &gt; 0$ people want to visit $c$. The integers $\eta_v$ are appear in increasing order when traversing $L$.

An array $N$ of $n$ elements. The $i$-th element $n_i$ of $N$, if initialized, is the number of people that want to visit the $i$-th city.

An array $P^L$ of $n$ elements. The $i$-th element $p^L_i$ of $P^L$, if initialized, is a pointer to the node $v$ of $L$ such that $\eta_v = n_i$.

An array $P^\ell$ of $n$ elements. The $i$-th element $p^\ell_i$ of $P^\ell$, if initialized, is a pointer to the node containing the $i$-th city in the list $\ell_v$, where $v$ is the node of $L$ pointed by $p^L_i$.


Init$(n)$:

Create an empty list $L$. Allocate (but do not inizialize) the arrays $N$, $P^L$, and $P^\ell$ in $O(1)$ time.

Visit$(\cdot,i)$:

If $n_i$ is initialized, delete (in constant time) the node pointed by $p^\ell_i$ from the list $\ell_v$ where $v$ is the node of $L$ pointed by $p^L_i$. If $\ell_v$ is empty, delete $v$ from $L$.  Increment $n_i$.

Otherwise, if $n_i$ is not initialized, set $\eta_i=1$.

Find the node $v'$ of $L$ such that such that $\eta_{v'}=n_i$, if it exists. Notice that $v'$ can only be the node of $L$ following (the possibly just deleted) node $p^L_i$ in $L$.

If $v'$ did not exists, then create it (in constant time).

Add city $i$ to a new node $z$ of $\ell_{v'}$.

Make $p^L_i$ point to $v'$.

Make $p^\ell_i$ point to $z$.


Favorite$(k)$:

Let $v$ be last node of $L$.
While $k&gt;0$ and $v$ exists:

Let $x$ be a pointer to the first node of $\ell_v$
While $k &gt; 0$ and $x$ exists:

Return the city stored in $x$.
Set $x$ to the vertex following $x$ in $\ell_v$ (possibly none).
Decrement $k$


Set $v$ to the vertex preceding $v$ in $L$ (possibly none).