t1
容易发现对于奇数和偶数，能满足条件的长度分别是单调的，所以可以分别二分答案检查。
检查的时候对于差分序列做哈希即可，然后用 set/map/哈希表 判 \(B\) 的子段是否有 \(A\) 的子段能匹配。
单哈希冲突概率很大，所以至少要双哈希，时间复杂度 \(O(n\log n)\) 到 \(O(n\log^2 n)\) 取决于判出现的容器。
t2
考虑枚举所有被删除的中最小的那个，如果有相同大小的，那么以下标作为第二关键字，就可以视作两两不等。
枚举之后，考虑总共要删 \(k\) 个，在这个位置之前删 \(x\) 个，之后删 \(k-x\) 个。
由于 \(k\) 很小，所以可以在前后分别找 \(k\) 个最靠近的大于枚举的数的数，如果按照数字从大到小枚举也就是所有已经考虑过的数中前后分别拿出最近的 \(k\) 个。
找数可以用链表维护，或者线段树，都能做到 \(nk\)。
枚举前面 \(x\) 个之后，左右端点的合法范围都是一个区间，用 \(ST\) 表维护前缀和的最大值和最小值即可。
时间复杂度 \(O(nk+n\log n)\)
t3
只有 \(1\) 操作看上去是困难的，考虑这个操作实际上在做什么事情。
会重复若干轮，如果 \(k\) 足够使得区间内的最大值都能变成次大值，那就变。
否则最大值集体减去 \(\lfloor \frac k {cnt}\rfloor\)，然后再对于前若干个再减一。
找分解线也可以线段树上二分。
取 \(\text{min}\) 操作，维护最大和次大，求个数，求和，这些东西都能用 \(\text{segment beats}\) 实现。
关键复杂度证明在于使最大值变成次大值的轮数。
这个是均摊 \(O(n)\) 的，假设 \(n,q\) 同阶。
考虑每一轮操作是一个让最大值变成次大值的过程。
称一个操作有意义当且仅当这个操作使得一个 从一开始就没有变过大小的数 减小。
容易发现每次 \(1\) 操作最多只有开头的 \(3\) 次是无意义的。
原因也很简单，手玩一下就会发现，如果想要一直无意义，那就得一直选之前被改过的。
也就是考虑之前的修改区间，用两次封掉修改区间的前后，再一次一定选的两个目前最大值之间，然后再下一次一定就会修改还未更改大小的数了。
有意义的操作次数显然是 \(O(n)\)。
时间复杂度：\(O(n\log n)\)，如果认为 \(\text{segment beats}\) 是单 \(\log\) 的话。
标签：log,230102,最大值,模拟题,枚举,哈希,操作,复杂度 From： https://www.cnblogs.com/hellojim/p/17031384.html