12月做题记录

✩ trick
✯ 会大部分，要\(tj\)提示
✬ 会小部分/完全没想到，看了\(tj\)才会
◈ 脑电波
✡ 有某一算法的神秘通用性质
⊗ 待补

• 12月做题记录
  • CF1725K Kingdom of Criticism
  • CF1446D2 Frequency Problem (Hard Version)
    • • • • 根号做法 ✬
          • 线性　✯✩

CF1725K Kingdom of Criticism

考虑并查集，每次把\([l,r]\)内存在的点都提出来分别挂到\(l-1/r+1\)上然后删除，如果没有\(l-1/r+1\)，新建一个点即可

注意到点的级别是\(O(N)\)级别的且增删对某个点都是\(O(1)\)的，所以总复杂度\(O(N\alpha(N))\)

CF1446D2 Frequency Problem (Hard Version)

如果给定的序列就没有绝对众数，那么直接输出\(n\)，否则考虑证明：

最终的答案中的众数中一定有原本的序列的绝对众数

如果不满足的话，显然可以把当前区间拓展且不劣

根号做法 ✬

考虑枚举最终的众数的数量，给一个阈值\(B\)，那么直接双指针维护即可得到每个左端点对应的最大的右端点

这里的复杂度是\(O(BN)\)的

考虑当数量\(>B\)时，此时同样为众数的其他数值只有\(O(\frac NB)\)个，现在再来枚举同为众数的数值

设最初的绝对众数为\(A\)，现在枚举的另一个为\(B\)，只需要给一个序列\(c_i\)赋值为\(c_i=\left\{\begin{aligned}&1&&a_i=A\\&-1&&a_i=B\\&0&&otherwise \end{aligned} \right.\)，那么只需要满足一个区间内的\(c_i\)的和为\(0\)即可，这个用前缀和即可处理

当然有可能会出现当前区间内真正的众数既不是\(A\)也不是\(B\)的情况，但显然这种情况是劣的，所以不管，复杂度\(O(\frac NBN)\)

取\(B=\sqrt N\)，则总复杂度\(O(N\sqrt N)\)

线性　✯✩

显然，如果我们依旧是枚举另一种值\(B\)，那么只需要找到最长的区间使得\(A\)的数量和\(B\)的数量相同，若他们不是这段区间的众数，那么这段区间一定劣

对于一个\(l\)，发现我们的最优区间\([l,r]\)满足\(a_{l-1}=A/B\)，\(a_{r+1}=A/B\)且\([l,r]\)内的\(A\)、\(B\)数量相等，若依旧沿用上面提到的\(c_i\)，注意到区间和的变化是连续的，也即说明，对于\(r'>r\)，那么\([l,r']\)一定全\(>0\)或全\(<0\)

考虑这样一种方法，枚举\(B\)的位置\(x\)，每次把\(x\)且没被标记的\(A\)的后继给标记，然后还原，然后再标记前驱，这里其实顺序无所谓，怎么弄都是那些点

显然此时从没被标记的\(A\)一定不会出现在最终的区间\([l,r]\)中，那么显然现在只有\(O(|A|)\)个点，直接用上面的\(1/-1\)的方法即可

只需要记录\(pre_i\)表示\(\leq i\)的\(A\)的最大位置和\(suf_i\)表示\(\geq i\)的\(A\)的最小位置即可做到线性

复杂度\(O(N)\)