牛客练习赛73 D 离别

离别

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

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

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

全部评论

相关推荐

专业嗎喽:个人信息名字太大,合到电话邮箱那一栏就行,有党员写过党,剩下其他全删,站空太大了 把实习经历丰富,放最前面,然后是个人评价,技能之类的,然后是学校信息。项目经历最后面,可以就选一个自己擅长的。 现在是学校不是92就扣分的,没必要放前面。 然后现在看重实习经历>竞赛经历(校园经历)>课程项目经历
点赞 评论 收藏
分享
评论
3
1
分享

创作者周榜

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