重回两题队轻松绷住，现在的重点问题是，看题不仔细，还是应该注意策略中的细节，既标注出可能的突破口（记录自己的观察）和可能忽略的点（眼睛瞎没看到，特别是现在两人队的时候）

J

赛时大概提出了一个线性dp的模子，但是处理只出现4次的时候太过麻烦了

采用随机化 hash 对每一种数前三个分配一个值，最后一个分配 $c_1 \oplus c_2 \oplus c_3$ ，这样就只有 $4k$ 次的时候才是 $0$

接下来保证是 4 次，维护指针代表可能的最左转移点，每次加入新数的时候，把指针和倒数第五次出现这个数的位置+1 取 $\max$ 即可

那么每次 hash 值为 $0$ 的所有在指针右侧的值都可以转移，动态维护这一部分的和即可

$O(n)$

F

更是难绷，没看到是排列

这个最重要的问题是要从 $n$ 的时候开始做，而不是从 $1$ 开始填

赛时队友提出了从前往后做，但是没法确定第一个填入的数，切入方向错了，所以要从后开始，这样第一个中位数一定是 $m$

接下来我们考虑每次删掉两个数之后有什么变化

首先记 $r_i$ 表示第 $i$ 个数要作为中位数出现多少次，初值为出现次数 $-1$

我们设从后往前删除当前 $1 \sim n$ 种还剩下的 $2k-1$ 个数的中位数为 $x$

那么此时选择后 $r_x \rightarrow r_{x}-1$ 我们要删掉的两个值就是当前最后填入答案序列的两个值，我们现在来判断选哪两个值

这个两个值左右删掉的一定是一样的策略，它们必须都是不可能成为中位数的值，也就是 $r_i=0$

首先 $x$ 如果 $r_x$ 减 $1$ 后变 $0$ 肯定要删掉它，下一步中位数肯定要左移或者右移，删掉它对左右两侧影响最小，肯定比再去找出来一个数优秀

否则我们就要左右都找出一个数来删掉，我们选择最近的 $r_i=0$ 的数，道理还是一样的，如果我们删掉一个比较远的值或者最远的值，这个已知的近值就浪费了，而且不好维护

然后如果剩余数排序后中位数的左侧仍然 $r_l \gt 0$ 我们就把中位数变成左边的，否则变成右边的，删除反向的最近 $r_i=0$ 的值

当然我们得想办法让这个策略变成合法的，我们首先要确保每次选的时候都能移动

最开始中位数为 $m$，删掉 $2t$ 个数后，设中位数为 $x_t$

那么 $m-t \leq x_t \leq m+t$，所以 $\sum_{m-t}^{m+t} r_i \geq t+1$

如果这样可行的话，每次删的时候 $r_l +r_x+r_r \geq 2$ 所以一定可以转移，而且每次我们删掉后也还是满足的

所以初始的判定 $-1$ 条件就是这个

$O(n\log n)$ 用 $\text{set}$ 实现