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 2821 >> - -求正解……
weixinding @ 2012-06-04 14:58:07
[ Quote ] [ Edit ] [ Delete ] 1#
想分块+主席树水过,发现TLE的厉害
jtc172 @ 2012-06-04 15:25:24
[ Quote ] [ Edit ] [ Delete ] 2#
弱弱地问一句。可不可以这样,将整个N个东西分成若干块,每块大小(NlogN)^1/2,然后首先预处理每块的起点到N的值,这个的时间复杂度是N*(NLogN)^1/2,然后处理询问时对块内元素二分求出现次数,也是N*(NlogN)^1/2,然后总的时间复杂度为(NlogN)^1/2*N。
weixinding @ 2012-06-04 15:44:38
[ Quote ] [ Edit ] [ Delete ] 3#
- -我大概也是这么写的……查出现次数本傻×还写了个主席树
这么写TLE的厉害所以才求正解……
jtc172 @ 2012-06-04 15:51:10
[ Quote ] [ Edit ] [ Delete ] 4#
我才是傻×啊,求不D啊。话说我说的是错的,空间会超,要改变存法。
weixinding @ 2012-06-04 16:00:08
[ Quote ] [ Edit ] [ Delete ] 5#
= =我存的每块起点到每块终点的答案
weixinding @ 2012-06-04 16:18:58
[ Quote ] [ Edit ] [ Delete ] 6#
- -主席树太慢了
二分比较快,二分范围比较短
zhouzhendong @ 2018-09-06 23:10:06
[ Quote ] [ Edit ] [ Delete ] 7#
bitset大法好!
https://www.cnblogs.com/zhouzhendong/p/BZOJ2821.html
[Top] [Previous Page] [Next Page]

HOME Back