隨機大法好

本次介紹隨機演算法最常用的 generator "mt19937"

你需要以下兩個函式庫

#include <random>
#include <chrono>

在使用 mt19937 前也要給它一個 seed (種子)

auto seed = std::chrono::steady_clock::now().time_since_epoch().count();
std::mt19937 rng(seed);

之後可以用 uniform_int_distribution 來取得指定範圍 $[l, r]$ 內隨機產生的數字

int Orz = uniform_int_distribution<int>(l, r)(rng);

於是乎它比C++內建的rand()強大許多，細節就不多贅述。

現在，給你一個序列長度為 $N$

有 $Q$ 筆詢問，每筆詢問區間 $[l_i, r_i]$ 內的絕對眾數

絕對眾數的定義為 某數的出現次數嚴格大於該區間元素數目的一半

如果不存在，輸出 0

Constraints:

$1 \leq N, Q \leq 3 \times 10 ^ 5$

$1 \leq a_i \leq 3 \times 10 ^ 5$

$1 \leq l_i \leq r_i \leq N$