[BZOJ3339/Luogu4137]Rmq Problem(主席树)

发布于 2018-05-28  408 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3339/Luogu4137]Rmq Problem(主席树)

Description

[BZOJ3339/Luogu4137]Rmq Problem(主席树)

Tag

主席树

解决思路

考虑对每一个位置维护一棵值域线段树,记录每一个值到当前的最晚出现时间。那么对于询问\([l,r]\),在值域线段树上二分,若左边的最小值小于\(l\)说明可以继续往左儿子走,否则向右儿子走。
由于每一位只修改一个地方的值,所以用主席树代替\(n\)棵线段树。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3339/Luogu4137]Rmq Problem(主席树)


HNCJ OIer