首页 > 代码库 > 【线段树】HDU 4747 MEX
【线段树】HDU 4747 MEX
通道:http://acm.hdu.edu.cn/showproblem.php?pid=4747
题意:mex(L, R)表示区间上第一个没出现的最小非负整数,对于序列a[],求所有的mex(L, R)的和
思路:就是求mex(1,1) + mex(1,2)+....+mex(1,n)
+mex(2,2) + mex(2,3) + ...mex(2,n)
+mex(3,3) + mex(3,4)+...+mex(3,n)
...+ mex(n,n)
可以知道mex(z,i),mex(z,i+1)...mex(z,n)是递增的,首先很容易求得mex(1,1),mex(1,2)......mex(1,n),因为上述n个数是递增的,然后使用线段树维护,需要不断删除前面的数。
比如删掉第一个数a[1]. 那么在下一个a[1]出现前的 大于a[1]的mex值都要变成a[1]
因为是单调递增的,所以找到第一个 mex > a[1]的位置,到下一个a[1]出现位置,这个区间的值变成a[1].
代码:https://github.com/Mithril0rd/Rojo/blob/master/hdu4747.cpp
TAG:好题,线段树维护
【线段树】HDU 4747 MEX
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。