F.A.Qs Home ProblemSet Status Ranklist 1 Contest LoginRegister
Notice:1:五月份月赛定于5.27日12:30--17:30,鸣谢Claris主持!欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
大视野在线测评-欢迎您
[ New Thread ]
Problem 2850 >> 求正解!
GXZlegend @ 2017-07-03 14:26:59
[ Quote ] [ Edit ] [ Delete ] 1#
裸KD-tree过了
然而我造出数据把自己的KD-tree卡掉了。。。
数据大概是这样的:
50000 50000
0 1 1
2 1 1
2 3 1
4 3 1
4 5 1
......

1 -1 0
1 -1 0
......
GXZlegend @ 2017-07-03 14:27:34
[ Quote ] [ Edit ] [ Delete ] 2#
上面是n个点,下面是m个询问
1098643527 @ 2017-07-03 14:28:33
[ Quote ] [ Edit ] [ Delete ] 3#
Orz
网上的题解基本都是用kdTree做的吧?(我也是QAQ)
CQzhangyu @ 2017-07-03 14:34:11
[ Quote ] [ Edit ] [ Delete ] 4#
Orz
网上的标程好像没有能过的。。。
GXZlegend @ 2017-07-05 12:45:19
[ Quote ] [ Edit ] [ Delete ] 5#
求不沉!
CQzhangyu @ 2017-07-05 19:39:12
[ Quote ] [ Edit ] [ Delete ] 6#
好像正解是整体二分+半平面交。。。蒟蒻不懂
user12345 @ 2017-12-08 10:06:21
[ Quote ] [ Edit ] [ Delete ] 7#
求数据
alone_wolf @ 2018-01-02 15:34:58
[ Quote ] [ Edit ] [ Delete ] 8#
http://codeforces.com/blog/entry/9660
用分块+主席树O(n根号log)时空预处理,O(根号log)询问的算法
用四分树来做分块,取块的个数为(n的(以12为底4的对数)次方)可以达到理论最优复杂度(假设n,m同阶):O(n*(n的(以12为底3的对数)次方)*logn)
把块的大小取的再小一点,降低一下预处理的空间复杂度或许能过?
alone_wolf @ 2018-01-02 18:35:52
[ Quote ] [ Edit ] [ Delete ] 9#
感觉离线就不用可持久化了,可以把空间降下来,但是时间没变
时间勉强可以接受吧-_-如果按一个点10s算的话
[Top] [Previous Page] [Next Page]

HOME Back