CF643G

线段树 + 众数的好题。

题意：给定长度为 $n$ 的序列和常数 $p$，$q$ 次操作，区间赋值或是查询区间出现次数大于 $p\\%$ 的数。可以有无关输出，但总数不能超过 $\left\lfloor\dfrac{100}p \right\rfloor$。$20\leq p\leq 100, n, q\leq 1.5\times 10 ^ 5$。

考虑 $p > 50$ 怎么做。维护一个 (x, cnt)，表示一个数和当前数出现次数减去非当前数的出现次数。显然 $cnt > 0$ 的数最多只有一个，也就是说，我们只需要维护一个 pair 即可。来了新的一个数时，如果等于当前数，显然 cnt ++，否则 cnt --。如果当前的 $cnt$ 已经 $\leq 0$ 了，说明这个数是不优的，一定不可能成为答案，我们就删除这个 pair。如果新来一个数时 pair 是空的，我们直接设置为 (x, 1) 即可。

考虑证明可行。显然一个数 $x$ 如果出现频率大于 $50\\%$，那么到最后的时候，他一定没有被其他数所换下，因为即使所有数都攻击 $x$ 的 $cnt$，最后仍然 $cnt > 0$，也就是不会被弹出。至此我们证明的这一定是可行的。

扩展该做法，维护 $\left\lfloor\dfrac{100}p \right\rfloor$ 个 (x, cnt)，如果来了一个数是其中的某一个数，直接对这个 (x, cnt) 加一。否则对每一个 (x, cnt) 减一，如果有 $cnt = 0$，则删除。显然如不满 $\left\lfloor\dfrac{100}p \right\rfloor$ 个的话，我们就设置一个 (x, 1) 即可。

考虑正确性。如果这个数被弹出仅当至少出现了 $\left\lfloor\dfrac{100}p \right\rfloor$ 个和他互不相同的数，并且这个数仅出现了一次，如果再出现这个数也至少有 $\left\lfloor\dfrac{100}p \right\rfloor$ 个和他不同的数，说明这个数的出现频率不可能达到 $p\%$，得证。

区间操作直接直接使用线段树维护即可，合并信息的时候可以将一边的数按照 cnt 次出现计算，暴力加入另外一边（显然没有出现在左右的 pair 中则不可能出现在最终的 pair 中）。假设 $k = \left\lfloor\dfrac{100}p \right\rfloor$，则时间复杂度为 $O(k ^ 2n\log n)$。

题外话：可不可以使用这个维护区间众数呢？欢迎在评论区留言。

using PII = std::pair<int, int>;

struct Major {
    PII dat[5];
    Major() {  }
    Major(int x, int cnt) { dat[0] = {x, cnt}; }
    PII& operator [](int x) { return dat[x]; }
} ;
int k; // 维护 k 个 pair

Major operator +(Major a, Major b) // 合并两边的 pair
{
    for (int i = 0; i < k; ++ i)
    {
        int x = b[i].first, cnt = b[i].second, flag = 0;
        for (int j = 0; j < k && !flag; ++ j)
            if (a[j].first == x) flag = 1, a[j].second += cnt;
        if (flag) continue;
        for (int j = 0; j < k && !flag; ++ j)
            if (!a[j].first) a[j] = {x, cnt}, flag = 1;
        if (flag) continue;
        int mx = 1e9, pos = -1;
        for (int j = 0; j < k; ++ j)
            if (chkmin(mx, a[j].second)) pos = j;
        if (cnt < a[pos].second)
            for (int j = 0; j < k; ++ j) a[j].second -= cnt;
        else {
            for (int j = 0; j < k; ++ j) a[j].second -= mx;
            a[pos] = {x, cnt - mx};
        }
    }
    return a;
}