- 博客(2)
- 收藏
- 关注
RSS订阅原创 关于treap启发式合并的一点脑洞(以bzoj2809为例)
首先我直到bzoj2809正解应该是可并堆，之所以写treap启发式合并单纯只是因为这个脑洞… 首先我们有两个treap，分别是 A 和 B ，它们的节点数分别为 n 和 m (n<m)(n<m)。网上普通的启发式合并是把 A 中的结点一个个扔进 B 里，这样复杂度是 O(nlogm)O(nlogm) 的。然而 zyqn 告诉我 myy 说这个事情可以做到 O(nlogmn)O(nlog\frac{
2017-01-30 22:28:45
894
原创 [bzoj4570][scoi2016]妖怪 二分区间
写在前面的话： 本题正解是凸包而不是二分，科学做法请右转各神犇blog。以下是蒟蒻的二分做法。 我的代码在不开o2的情况下大约800ms-900ms一个点 开o2大约300ms-400ms一点。 首先设k=abk=\dfrac{a}{b}，记xi=atki,yi=dnfix_i=atk_i,y_i=dnf_i 则对于每个1≤i≤n1\leq i\leq n，战斗力为fk(i)=(1k
2016-05-30 22:14:38
409
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人