牛客练习赛73 D 离别
离别
https://ac.nowcoder.com/acm/contest/9033/D
感谢大佬提供的
思路
我稍微写的详细一点qwq
发现可以把询问离线下来，每次询问的答案就是
的答案减去
的答案。
问题转变为了如何求的答案：
在询问，一种最直接的想法就是直接枚举
使得
。
但是我们已经转化为的答案，所以我们可以对每个位置
预处理出一个最小
使得
中出现次数最多的数出现了
次，然后我们可以直接枚举
，
就可以取
的位置，即可以有
种取法
总的取法就是
预处理开
看当前颜色后面第
个颜色的位置，然后从后往前取
就行了。
所以是有单调性的，我们可以设
为
的最大的数，然后枚举
的时候移动
。
当时，答案为
当时
答案就变成了
运用结合律，答案就变成了
就是
我们可以预处理前缀和，就可以
计算每个询问了
总的复杂度就是了
当然您也可以三指针一遍搞出来
我的代码
