删除后面一段?什么意思?
by longlongzhu123 @ 2019-04-19 16:32:55
@[longlongzhu123](/space/show?uid=57525) 你不断复制的话长度会变成指数级,这样复杂度肯定是不对的
by 142857cs @ 2019-04-19 16:43:29
所以要把一定不会访问到的部分删除
by 142857cs @ 2019-04-19 16:44:50
@[142857cs](/space/show?uid=35760) 不一定啊,可以不断复制`[1, 100000]`这一段嘛
然后设置一个删除操作,复制完就随便找几个位置删掉
而且就算是指数级的也没问题,复杂度仍然正确$O(N\log_2N)$
by longlongzhu123 @ 2019-04-19 16:48:04
@[longlongzhu123](/space/show?uid=57525) 等等,当我没说
如果不删除的话是$O(N^2)$的
by longlongzhu123 @ 2019-04-19 16:49:00
如果有删除就可以NlogN
by longlongzhu123 @ 2019-04-19 16:49:58
@[longlongzhu123](/space/show?uid=57525) 您有相关题目吗?或者有没有私有的板子题?我只是想看一下。。
by Utsuji_risshū @ 2019-04-19 17:06:40
P3814 考了
by 小粉兔 @ 2019-04-19 17:18:10
@[142857cs](/space/show?uid=35760) 为什么用treap...用替罪羊树不是更好吗。。。
by ecnerwaIa @ 2019-04-19 17:28:03
替罪羊树能分裂区间么。。。
by ecnerwaIa @ 2019-04-19 17:29:05