vijos_sft_minmax

题目链接

线段树练习_vijos_sft_minmax

题解

暂时还没有合适大小的数据可以上传…

自测数据5个测试点1个\(G\)…

但是这道题很膨胀

这还是一道线段树.

但是看着像是链表和数组的结合体的题..

然鹅链表+数组=\(TLE\)

大概是什么块状链表的大暴力吧..

\(O(NlogN)\)可以过,但是\(O(N\sqrt N)\)还过不去..

算一下大概\(10^9\)


正解:线段树

删除+区间查询.

??????

线段树删除????

还有这种操作???


对于特殊类型的线段树的话,我们需要一点点平衡树的知识不需要

平衡树找前驱后继的时候,是根据其\(size\)大小来查的.

这个线段树的节点就不是存值了,(当然可以开一个结构体)废话

是用来存节点大小的.

查询的时候比较左右\(size\)和节点大小就好了.

查询分三种情况.

  • 1.查询区间左端点比当前左节点的\(size\)小,右端点比左节点\(size\)大,证明区间在左右子树中,查询两次
  • 2.查询区间左端点比左子节点\(size\)小,右端点比左子节点\(size\)小,查左子树
  • 3.查询区间左端点比左子节点\(size\)大,右子节点也比它大,查右子树

即区间包含(跨区间)、纯左区间、纯右区间,三种.

删除分两种

  • 1.删除\(num\)比左\(size\)小,递归左
  • 2.删除\(num\)比左大,递归右

没了…

Orz线段树….


update.

记得init要在build前面!!!!

不用像我调半个小时发现是init的问题


By:Wahacer

2017.12.19

10:21

发表评论

电子邮件地址不会被公开。 必填项已用*标注