摩爾投票法
絕對衆數 ：數列内出現次數超過數列長度一半的數。
摩爾投票法是一個求絕對衆數的利器。
例題
1. 洛谷 P2397 yyy loves Maths VI (mode)
摩爾投票法闆子題。
假設現在有一個小房子，有一個新的數 \(x\) 需要進來。
- 如果房子是空的，那麼 \(x\) 就直接進去；
- 如果房子内的數和 \(x\) 相等，那麼 \(x\) 也進去；
- 否則把房子内的其中一個數帶出房子。
其實本質是将衆數與其他數配對，然後抵消掉。因為衆數出現次數大于一半，是以最後留在房子裡的數一定是衆數。
2. P3765 總統選舉
用線段樹維護區間内出現次數超過一半的數 \(num\) 以及它的出現次數與其他數的出現次數之和的差 \(cnt\)。
顯然可以合并。合并時分類讨論兩個兒子的 \(num\) 是否相等：
- 若相等，則目前結點的 \(num\) 就是兒子的 \(num\)，\(cnt\) 就等于兩個兒子的 \(cnt\) 的和；
- 若不相等，則目前結點的 \(num\) 是 \(cnt\) 更大的兒子的 \(num\)，\(cnt\) 為兩個兒子的 \(cnt\) 之差的絕對值。
然而此題還要讨論衆數出現次數不超過區間長度一半的情況。若不考慮空間，可以對每一個數開一個動态開點線段樹記錄它在哪些位置出現過。這樣查找一個數的出現次數隻用詢問區間和。然而這樣做的空間複雜度是 \(O(n \log \sum k_i)\)，無法承受。是以隻能開 \(n\) 棵平衡樹，每次 \(\mathrm{insert}\) 或 \(\mathrm{erase}\) 相應的位置，然後查詢出現次數就找到對應的平衡樹，\(r\) 的 \(\mathrm{rank}\) 與 \(l - 1\) 的 \(\mathrm{rank}\) 相減即可。
3. P8496 [NOI2022] 衆數
每個數列開一棵動态開點線段樹，按前一題的方法 \(\mathrm{merge}\)。插入、删除就用連結清單維護，注意存每個連結清單的頭元素和尾元素。查詢時将對應數列的 \(\mathrm{root}\) \(\mathrm{merge}\) 一下即可。對于操作 \(4\)，合并一下兩個連結清單和兩棵線段樹即可。