概述
题目链接：
M-Stone Games_第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（昆明）（重现赛） (nowcoder.com)
对于【L,R】区间所能表示的【1，x】，其中x即是所能表示的连续的最大值，也就是表示不了x+1了，记不能表示的最小值为mex
如何扩展？
对于a[r+1]来说：
如果a[r+1]>x+1,那么肯定表示不了x+1,有效值域还是原来的【1，x】
如果a[r+1]<=x+1，那么有效值域就能扩展到【1，x+a[r+1]】
所以我们可以根据数列中数值<=x+1的数的前缀和>=mex,如果符合条件就可以扩展，反之不能。
因此如果我们让这段区间是有序的话，就能快速找到小于等于mex的前缀和，直到某区间无法扩展，即，x+sum<mex,答案就出来了。
这样对于每一次查询，就能用将近log（n)的速度求出，因为一个区间的扩展是很快的我估计就是常数级别而已）
如何实现：
使用主席树：
这种数据结构能做到上面的要求（有序，快速求和）。就是普通的主席树加上二分查找一下就行了，实现起来也非常简单70行左右，对主席树熟悉的手快的三分钟就能打完。
最后
以上就是柔弱羊为你收集整理的2021-ICPC昆明站M-Stone Games（思维+主席树）的全部内容，希望文章能够帮你解决2021-ICPC昆明站M-Stone Games（思维+主席树）所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复