[HDU4417]Super Mario(主席树)

发布于 2018-01-26  7 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4417]Super Mario(主席树)

Description

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

Http

HDU

Tag

主席树

题目大意

求区间内小于给定的\(K\)的数的个数

解决思路

离散化并去重之后,用主席树维护权值线段树,类似前缀和地查询即可。
有点卡时,要手写二分+去重才行

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU4417]Super Mario(主席树)


HNCJ OIer 一枚