F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 3065 >> 用平衡树套线段树真的可以n*log(n)^2吗?
Patchuli_Go @ 2017-03-13 14:01:06
[ Quote ] [ Edit ] [ Delete ] 1#
n*log(n)^2的结论来源于线段树合并是nlogn的。
但是线段树合并里有这么两句话:
if(!a) return b;
if(!b) return a;
一个节点为空,那么所创建的节点就会与另一个节点共用子树。
但是本题里平衡树某个节点构造线段树时并不能破坏儿子的线段树,如果可持久化使一个线段树与儿子的线段树共用某些节点,替罪羊重建时底下线段树节点的更改就会影响没被重建的祖先部分。
所以求问用平衡树套线段树A掉此题的做法,是否可以做到n*log(n)^2。
Rcapor @ 2017-03-13 14:17:23
[ Quote ] [ Edit ] [ Delete ] 2#
您和我开始的想法一样
其实暴力插就可以了,不用写线段树合并。
复杂度是对的
alone_wolf @ 2017-03-13 18:01:25
[ Quote ] [ Edit ] [ Delete ] 3#
为什么是对的啊
Rcapor @ 2017-03-13 19:06:08
[ Quote ] [ Edit ] [ Delete ] 4#
把一个点插进去会使得平衡树上(树高)个点的线段树需要更新,一次log^2
重构的时候也暴力插,一样道理
nzhtl1477 @ 2017-03-13 22:48:30
[ Quote ] [ Edit ] [ Delete ] 5#
讲道理平衡树合并也是nlogn的还比线段树合并快
stealthassassin @ 2017-03-13 23:21:50
[ Quote ] [ Edit ] [ Delete ] 6#
orz由乃,ds大佬
nzhtl1477 @ 2017-03-14 00:40:23
[ Quote ] [ Edit ] [ Delete ] 7#
什么鬼。。。
zhhx @ 2017-12-18 08:22:10
[ Quote ] [ Edit ] [ Delete ] 8#
不是很明白。为什么暴力插入log^2是对的?
[Top] [Previous Page] [Next Page]

HOME Back