6
18
2016
0

【NOI模拟赛#3 T2】【主席树套线段树】【倍增】线段树Segment

题意:

Tag:

线段树维护区间并

可持久化线段树计算“前一个覆盖到这个端点的操作”

预处理倍增数组快速完成遍历

分析:

对于每个询问位置k,找到当前操作区间[L,R]中包含该位置的最靠后的操作区间,设为第H个操作区间[l[H],r[H]]。

则k位置最终的值为进行完操作[L,H-1]后,区间[l[H],r[H]]的最小值:可能受到H前与H相交的区间影响,也可能最大值出现在H中。

那么对于当前询问,从后到前将有交集的区间取并,将[l,r]扩展到H所在的并区间,然后取该区间最大值即可。

暴力模拟 O(q(n+m))

 

Category: RMQ | Tags: 可持久化数据结构 树套树 分块 区间问题 倍增 | Read Count: 751

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com