CF643G Choosing Ads

题意：给定一个长度为 的序列和整数参数 。

有 个操作：

• 区间赋值

• 找出区间内出现次数达到 的数。

  允许多余(错误)输出，但是回答的数的个数不得超过 。

，，时限 。

---

令 。

• 做法一

首先能够发现,若某个数在 中出现达到 ,那么其必然也在 的其中一个区间中出现达到 。

这就给我们合并信息创造了条件。

设 ，在每个区间内我们只需要维护 个数。

我们可以用一棵线段树维护连续段和拆散的情况，当只有区间赋值的时候总共只会产生 次相关操作。再对每种数使用动态开点线段树维护区间赋值信息。

这样能做到 取得某个区间内 的出现次数。

现在我们得到了一个时间 ，空间 的做法，而且实现较为繁琐。

• 做法二

继续观察性质。

令 ，即区间严格众数。

有一种经典的做法（摩尔投票）：每次将不同的对子消去，最后若能剩下数，则一定是严格众数。

注意，这对消除的顺序没有任何要求。我们可以先把整个区间分成两个部分，部分内部消完，合起来再消，正确性还是有保障的。

考虑使用线段树维护这个过程。只需维护剩下的数是谁，以及剩下的出现次数即可。

维护区间众数及其 HP，若合并两个相同的数，则 HP 叠加。否则 HP 对消并取活下来的那个。

接下来扩展到 的情况，不难发现，若每次消掉 个不同的数，最后剩下的 个不同的数即为答案。

证明：我们最多删去 组数,而答案中的数都必然出现严格多于 次。

可以 暴力完成一轮 对 的消除。复杂度 。