概述

摩尔投票算法用于求解区间中出现次数严格大于 $len / k$ 的数。

普通摩尔投票

普通摩尔投票只能解决 $k = 2$ 时的问题。

我们先考虑一个暴力的方法。维护当前答案 $x$，和 $x$ 的权值 $c$。依次扫描 $l$ 到 $r$ 的每个数。

假设当前数为 $a$：

  • 如果 $x = a$，那么将 $c$ 加上 $1$
  • 否则，将 $c$ 减去 $1$。如果 $c$ 减去 $1$ 会变成负数，那么将 $x$ 赋值为 $a$，并将 $c$ 设为 $1$

如果次区间存在出现次数严格大于 $len / 2$ 的数，那么它就是 $x$。因为 $x$ 的出现次数严格大于 $len / 2$，其他所有数都不可能在最终把 $c$ 消成负数。

Misra - Gries 算法

回到原问题，现在 $k$ 可能不是 $2$ 了。

出现次数严格大于 $len / k$ 的数最多有 $k - 1$ 个，我们需要维护这 $k - 1$ 个数。记为 $x_1, \ldots, x_{k - 1}$ 和 $c_1, \ldots, c_{k - 1}$。

仿照普通摩尔投票。依次扫描 $l$ 到 $r$ 的每个数。

假设当前数为 $a$：

  • 如果 $x_i = a$，那么将 $c_i$ 加上 $1$
  • 否则，如果存在一个 $c_i = 0$，将 $x_i$ 设为 $a$
  • 否则，将所有 $c_i$ 全部减掉 $1$

我们用反证法证明。假设有一个出现次数大于 $len / k$ 的数 $f$，并不在 $x$ 中。设 $f$ 在区间中的出现次数为 $cnt$。$f$ 被删除了 $cnt$ 次，每次会删除 $k$ 个数，所以一共删除了 $k\cdot cnt$ 个数，但是 $cnt > len / k$，因此 $k \cdot cnt > n$，显然矛盾。

由于我们不依赖元素顺序，因此有交换律和结合律。显然可以用线段树维护区间的投票结果。合并是 $O\left(k\right)$ 的。

单次区间查询复杂度为 $O\left(k \log n\right)$。

也可以支持区间覆盖等修改。

代码

https://codeforces.com/contest/643/problem/G

tp Q;
 
int WITHERING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
   tp n, q, pp; cin >> n >> q >> pp;
   Q = 100 / pp;
   struct S {
      tp len;
      array<tp, 5> v;
      array<tp, 5> c;
      
      S(tp len = 0) : len(len) { v.fill(-1); c.fill(0); }
      
      void add(tp x, tp cnt) {
         for (tp i = 0; i < Q; ++i) {
            if (v[i] == x) { c[i] += cnt; return; }
         }
         for (tp i = 0; i < Q; ++i) {
            if (c[i] == 0) { v[i] = x; c[i] = cnt; return; }
         }
         tp t = min(cnt, *min_element(c.begin(), c.begin() + Q));
         cnt -= t;
         for (auto& i : c) i -= t;
         for (tp i = 0; i < Q; ++i) {
            if (c[i] == 0) { v[i] = x; c[i] = cnt; return; }
         }
      }
      
      static S op(S a, S b) {
         a.len += b.len;
         for (tp i = 0; i < Q; ++i) a.add(b.v[i], b.c[i]);
         return a;
      }
      
      static S e() { return S(); }
      
      static S mapping(pair<tp, tp> t, S s) {
         if (t.first == -1) return s;
         s = S(s.len);
         s.add(t.second, s.len);
         return s;
      }
      
      static pair<tp, tp> composition(pair<tp, tp> s, pair<tp, tp> t) {
         return max(s, t);
      }
      
      static pair<tp, tp> id() { return pair(-1, -1); }
   };
   vector<S> zqr(n);
   for (tp i = 0; i < n; ++i) {
      tp x; cin >> x;
      zqr[i] = S(1);
      zqr[i].add(x, 1);
   }
   lib::Segtree<S, S::op, S::e, pair<tp, tp>, S::mapping, S::composition, S::id> o(zqr);
   for (tp z = 0; z < q; ++z) {
      tp op, l, r; cin >> op >> l >> r;
      --l; --r;
      if (op == 1) {
         tp x; cin >> x;
         o.apply(l, r, pair(z, x));
         continue;
      }
      S p = o.prod(l, r);
      vetp tar;
      for (tp i = 0; i < Q; ++i) {
         if (p.v[i] != -1) tar.push_back(p.v[i]);
      }
      cout << tar.size();
      for (auto& i : tar) cout << ' ' << i;
      cout << '\n';
   }
   return 0;
}