牛客练习赛73 D 离别

离别

https://ac.nowcoder.com/acm/contest/9033/D

感谢大佬提供的思路
我稍微写的详细一点qwq
发现可以把询问离线下来,每次询问的答案就是的答案减去的答案。
问题转变为了如何求的答案:
在询问,一种最直接的想法就是直接枚举使得
但是我们已经转化为的答案,所以我们可以对每个位置预处理出一个最小使得中出现次数最多的数出现了次,然后我们可以直接枚举就可以取的位置,即可以有种取法
总的取法就是
预处理看当前颜色后面第个颜色的位置,然后从后往前取就行了。
所以是有单调性的,我们可以设的最大的数,然后枚举的时候移动
时,答案为

答案就变成了
运用结合律,答案就变成了
就是
我们可以预处理前缀和,就可以计算每个询问了
总的复杂度就是
当然您也可以三指针一遍搞出来
我的代码

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 12:10
直接上图
牛客13578115...:改得一般,不值80
点赞 评论 收藏
分享
程序员小白条:这比例牛逼,750:1
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务