窩耍毒瘤QQ

題敘

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

提示

Hint 1

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

Hint 2

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

Hint 3

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

Hint 4

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

想法

觀察

可以發現一個區間的答案跟是否有絕對眾數有關。
而且，區間數字的順序不影響答案。
設區間長度為$len$，區間眾數出現$cnt$次，
則有一個方法永遠是最佳解：
把每個絕對眾數跟其他數兩個兩個一組，
這樣每一組不論放在哪個子序列都不會影響解的正確性，
所以答案就是剩下未分組的元素，
答案就是$len - (len - cnt) \times 2 = cnt \times 2 - len$，
沒有絕對眾數的答案就是$1$，所以答案就是$max(1\mathop{,} cnt \times 2 - len)$
　　

套用資料結構

有莫隊優化的作法，複雜度$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})$，
不過常數頗大，有沒有方法再更快？
　　
首先有一個線性判斷絕對眾數的方法，稱為摩爾投票法(俗稱戰鬥線段樹)，
過程是相同cnt+​+，不同cnt-​​​​​​-，cnt = 0就直接換數字，
這樣做並不保證是絕對眾數，但我們只要用前面的方法做一次就有答案了，
由於絕對眾數問題是無序的，所以可以透過線段樹作區間合併，
合併的規則就是相同cnt相加，不同就比大小再決定怎麼相減，
這樣區間查詢就縮到$O(\log N)$，
可以有很好的複雜度$O(N \log{N} + Q \log N)$且常數不大。
　　

AC Code

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