[問題案] Static Range Mode Query

[NachiaVivias]

Problem name: Static Range Mode Query
Problem ID: static_range_mode_query

Problem

空でない数列 $X$ の最頻値とは、現れる回数が最大であるような要素のこととします。

長さ $N$ の整数列 $A _ 0 , A _ 1 , \ldots ,A _ {N-1}$ に対して、 $Q$ 個のクエリを処理してください。

クエリ： $l,r$ が与えられるので、 $(A _ l , A _ {l+1} , \ldots , A _ {r-1})$ の最頻値を求めてください。最頻値が複数存在する場合はどれでもよいです。また、その数列にその値が現れる回数を求めてください。

Constraint

• $1 \leq N \leq 10^5$
• $0 \leq l \lt r \leq N$
• $0 \leq A_i \lt 10^9$

Solution / Reference

• https://noshi91.hatenablog.com/entry/2020/10/26/140105
• ↑から論文が辿れる： https://cs.au.dk/~larsen/papers/linear_mode.pdf

Input / Output

いつもの

Note

• originally posted by noshi91 : チェックしたいライブラリ #3 (comment)

[NachiaVivias]

• (1) 座圧を入れるかどうか
• (2) 出力を一意にさせるかどうか

[maspypy]

$A_i \leq 10^9$ でもいいと思います。座圧せず Mo して TLE するのはわりと見かけるやらかしだと思います。
出力は一意にしないでよいと思っています。設定が自然なので。

誤植指摘： $r\leq N-1$ → $r\leq N$

[NachiaVivias]

誤植修正しました。 $A_i$ の範囲は Static Range Inversions Query に倣う意味も含めて $0 \leq A_i \leq 10^9$ にします。

[maspypy]

作業者募集。

[maspypy]

作ります。