F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 2333 >> 这道题用可并堆不对吧?
elegant @ 2016-04-19 00:02:49
[ Quote ] [ Edit ] [ Delete ] 1#
可并堆的深度是O(n)的,不能像平衡树那样从根暴力下传标记。
我弄的数据生成器如下,好像网上很多人的可并堆都过不了。。。
讲道理这个生成的数据远没达到题面标注的极限范围。。
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
freopen("data.txt","w",stdout);
int n=10000, m=39999;
printf("%d\n", n);
for (int i=1; i<=n; ++i) printf("%d %c", min(i, 990), i==n?'\n':' ');
printf("%d\n", m);
for (int i=2; i<=n; ++i) printf("U %d %d\n", i, 1);
m -= n-1;
for (int i=1; i<=m; ++i)
if (i&1) printf("A2 1 %d\n", ((i-1)/2)&1 ? 1 : -1);
else printf("F1 1\n");
return 0;
}
szzq @ 2016-04-22 10:24:52
[ Quote ] [ Edit ] [ Delete ] 2#
2333快去加强数据ovo
nzhtl1477 @ 2016-04-26 00:42:39
[ Quote ] [ Edit ] [ Delete ] 3#
也不是所有可合并堆的深度最坏都是O(n)的呀~
有严格O( logn )的,解决这道题复杂度是对的
不过赞成加强数据
貌似这题的数据精心构造使得左偏树什么的跑的飞起233
elegant @ 2016-05-01 19:18:17
[ Quote ] [ Edit ] [ Delete ] 4#
主流的可并堆大概有左偏树,斜堆和随机堆。根据某大神的论文,前面两个的深度好像都是O(n)的,并且都是深度越接近O(n)越平衡。随机堆我不清楚,不过测出来也会T掉。。
1430586275 @ 2016-05-02 08:33:13
[ Quote ] [ Edit ] [ Delete ] 5#
这道题好像因为数据弱,然后一波可并堆就可以过掉了
nzhtl1477 @ 2017-02-17 16:01:50
[ Quote ] [ Edit ] [ Delete ] 6#
有一个膜法的可并堆是严格log深度哟~
Drench @ 2017-04-12 21:31:15
[ Quote ] [ Edit ] [ Delete ] 7#
有一种由乃可并堆高度是严格logn的啊~
GEOTCBRL @ 2017-04-13 21:54:00
[ Quote ] [ Edit ] [ Delete ] 8#
两棵大小分别为n,m,(n<m)的treap的合并复杂度是O(\binom{n+m}{n})=O(n\log (m/n))的。。treap做这个还是挺对的吧。。
LCF @ 2017-04-14 09:05:55
[ Quote ] [ Edit ] [ Delete ] 9#
这道题可并堆有复杂度对的做法呀……
只要把标记打在堆顶,每次合并的时候把siz小的堆的标记暴力下传给每个节点
再弄个并查集什么的维护一下堆顶就可以了
LCF @ 2017-04-14 09:10:00
[ Quote ] [ Edit ] [ Delete ] 10#
哦,siz小的那个堆里的每个元素还要减去另外一个堆堆顶的标记
jszyxw @ 2017-05-04 12:13:12
[ Quote ] [ Edit ] [ Delete ] 11#
lydsy hotter
yyuyang3 @ 2017-05-05 16:28:03
[ Quote ] [ Edit ] [ Delete ] 12#
9L 的做法可以过LZ给的生成的数据,但是下传标记的复杂度怎么算……
dxymaster @ 2017-10-18 18:29:16
[ Quote ] [ Edit ] [ Delete ] 13#
有一种由乃是严格log深度哟~
doggy_fxy @ 2017-10-18 19:10:42
[ Quote ] [ Edit ] [ Delete ] 14#
有一种由乃是严格log深度哟~
[Top] [Previous Page] [Next Page]

HOME Back