F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3731 >> 求标算?
GXZlegend @ 2017-09-28 20:38:28
[ Quote ] [ Edit ] [ Delete ] 1#
网上的块状树被手造的极限数据卡了个遍。。。
然而并不知道正解,因此没有加这道题的数据。

所以这题正解是啥?

P3720可以使用替罪羊树套Treap维护DFS序的方法过(块状树同样会被卡)
本题多了区间删除(区间分裂),难道正解是 块状链表套Treap/权值线段树/排序后的数组 ?
(然后常数不是一般的小。。。)

所以哪位Dalao写的不是块状树,分享一下做法呗。。。
GXZlegend @ 2017-09-28 20:39:47
[ Quote ] [ Edit ] [ Delete ] 2#
附数据做法:
(1)菊花图,可以卡掉大多数题解;
(2)初始一条链,然后在链的每一个节点处添加一个节点,再查询整棵树。可以卡掉全部(?)题解
GXZlegend @ 2017-09-28 20:40:21
[ Quote ] [ Edit ] [ Delete ] 3#
PS:两个图都需要插入叶子节点,而不是一开始就建出来整棵树
GXZlegend @ 2017-09-29 06:58:59
[ Quote ] [ Edit ] [ Delete ] 4#
顶上去
EdwardFrog @ 2017-09-29 07:02:05
[ Quote ] [ Edit ] [ Delete ] 5#
啊♂
GXZlegend @ 2017-09-29 15:41:26
[ Quote ] [ Edit ] [ Delete ] 6#
顶上去。。。
GXZlegend @ 2017-09-30 10:41:08
[ Quote ] [ Edit ] [ Delete ] 7#
顶上去>_<
GXZlegend @ 2017-09-30 10:42:44
[ Quote ] [ Edit ] [ Delete ] 8#
顶上去^_^
Superbia_zyb @ 2017-09-30 10:44:27
[ Quote ] [ Edit ] [ Delete ] 9#
顶上去^_^
GXZlegend @ 2017-09-30 15:29:31
[ Quote ] [ Edit ] [ Delete ] 10#
顶上去*_*
fhp1998 @ 2017-09-30 18:53:06
[ Quote ] [ Edit ] [ Delete ] 11#
3720和这个题,均可以采用询问分块的做法,类似于vfk对带插入区间k小值的最后那个根号做法,复杂度是有保证的,可以参考vfk的博客
walker90 @ 2018-06-02 22:30:12
[ Quote ] [ Edit ] [ Delete ] 12#
顶♂上去
[Top] [Previous Page] [Next Page]

HOME Back