窩耍毒瘤 QQ

題敘

有一個陣列， 多筆詢問一個區間 $[l, r]$， 問這個區間可以最少被分成多少個可以不連續的子序列， 使得每個分別的子序列中最常出現的數都不超過 $\Big\lceil \frac{\ell}{2} \Big\rceil$，其中 $\ell$ 是子序列的長度。

提示

Hint 1

一個區間的答案是 $1$ 或其他數跟什麼性質有關？
　　

Hint 2

假如只詢問一個區間，眾數的數量跟答案有什麼關係？
　　

Hint 3

現在知道全域的做法，要怎麼有效的維護絕對眾數（出現數量過半的數字）？
　　

Hint 4

有什麼資料結構／算法可以解決這個問題？
　　

想法

觀察

可以發現一個區間的答案跟是否有絕對眾數有關。 而且，區間數字的順序不影響答案。

設區間長度為 $\ell$，區間眾數出現 $c$ 次， 則有一個方法永遠是最佳解： 把每個絕對眾數跟其他數兩個兩個一組， 這樣每一組不論放在哪個子序列都不會影響解的正確性。

所以答案就是剩下未分組的元素， 就是 $\ell - (\ell - c) \times 2 = c \times 2 - \ell$， 沒有絕對眾數的答案就是 $1$，所以答案就是 $\max(1, c \times 2 - \ell)$。 　　

套用資料結構

有莫隊優化的作法，複雜度 $O(N \sqrt{N})$，已經能 AC 了。
　　
不過這樣並不夠好（雖然能 AC）， 如果一個陣列中某個是是絕對眾數，他左右半至少有一個子陣列絕對眾數也一樣， 所以可以考慮線段樹維護這個性質， 把查詢區間的 $\log N$ 個節點範圍內的區間絕對眾數都求一次取max， 而每個數的出現次數可以套vector用二分搜（當然也可以用動態開點線段樹，像我就這樣毒瘤）， 這樣複雜度是 $O(N \log N + Q \log^2{N})$，也夠 AC。
　　
當然如果不想這樣麻煩也可以區間內隨機取 $p$ 個數， 沒有選到絕對眾數的機率是 $2^{-p}$， 只要取 $40$ 個上下就夠， 理論複雜度是 $O(40 Q \log{N})$， 不過常數頗大，有沒有方法再更快？ 　　
首先有一個線性判斷絕對眾數的方法，稱為摩爾投票法（俗稱戰鬥線段樹），
過程是相同 counter+​+，不同 counter-​​​​​​-，cnt = 0 就直接換數字， 這樣做並不保證是絕對眾數，但我們只要用前面的方法做一次就有答案了， 由於絕對眾數問題是無序的，所以可以透過線段樹作區間合併， 合併的規則就是相同 counter 相加，不同就比大小再決定怎麼相減， 這樣區間查詢就縮到 $O(\log N)$， 可以有很好的複雜度 $O(N \log{N} + Q \log N)$ 且常數不大。 　　

AC Code

注意我的區間查數量毒瘤了 QAQ，所以建議不要參考，這題實作難度不高。
Link