Official Analysis

Explanation

We can subtract $n$ from each query, sort the cities by occurrences and the queries by year, and then answer the queries offline.

Let city $i$ denote the $i$'th smallest city sorted by occurrences, and $occ_i$ represent the number of occurrences. We can loop through each $i$ and track the years that have passed.

Assume cities $1, 2, \dots i$ already have $occ_i$ occurrences. For them to all end up with $occ_{i+1}$ occurrences, we need $i \cdot (occ_{i+1} - occ_i)$ more years, meaning that for the next $i \cdot (occ_{i+1} - occ_i)$ years, cities $1, 2, \dots i$ will be selected one after another.

To answer individual years, we can use a BST to track the initial indices of each city $1, 2, 3 \dots i$. Note that initial indices, not the sorted ones, break the tie for occurrences.

Let the current year be $y$. At each iteration, we can answer every query $q$ in the range of $y \leq q < y + i \cdot (occ_{i+1} - occ_i)$ and use binary search to obtain the indices of these queries. Since these cities are selected one after another, the answer to query $q$ is just the $(q - y) \% i$'th city sorted by initial indices.

At this point, we know every city has the max occurrence, so the answer to remaining queries that ask for years after the final $y$ is just $(q - y) \% m$.

Implementation

Time Complexity: $\mathcal{O}(m \log q \log m)$

Copy
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

using ll = long long;
#define all(x) x.begin(), x.end()