div4没打，感觉我的做法做赛时很难冲出来，毕竟前面还有 \(7\) 题。 思路： 考虑转化题意，即求得一段区间使得 不等于 \(k\) 的数的出现次数 减去 \(k\) 的出现次数 最小化。 显然如果
div4没打，感觉我的做法做赛时很难冲出来，毕竟前面还有 \(7\) 题。
思路：考虑转化题意，即求得一段区间使得不等于 \(k\) 的数的出现次数减去 \(k\) 的出现次数最小化。
显然如果 \(k\) 是选中的数，答案区间 \(l\) 和 \(r\) 必然有 \(a_l=a_r=k\)。
那么考虑枚举 \(k\) 并记录每个数出现的位置，即 \(g_{i,j}\) 表示 \(i\) 第 \(j\) 次在原数组 \(g_{i,j}\) 这一位置出现。
那么对每一个 \(k\) 枚举右端点，显然只有 \(n\) 种。
利用 \(g\) 数组对每一种 \(k\) 的右端点 \(r\) 找最优的左端点 \(l\)，那么就是对于 \(l<r\) 求 \(g_{k,r}-g_{k,l}+1-2\times(r-l+1)\) 的最小值；
解释一下：其中的 \(g_{k,r}-g_{k,l}+1-(r-l+1)\) 是求得这段区间内除以 \(2\) 的次数，再减去一次 \(r-l+1\) 就求得了最终要除多少次。
然后对 \(g_{k,r}-g_{k,l}+1-2\times(r-l+1)\) 分组，分成 \(g_{k,r}-2\times r-1\) 的和剩下 \(2\times l-g_{k,l}\)，显然前者是常数，需要最大化后者，后者对于每个 \(l\) 形式都一样，直接线段树维护即可。
代码：link实现细节较多，此代码思路并不清晰。