F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 4941 >> 这个做法没有错吧:
save_code @ 2017-12-04 08:50:01
[ Quote ] [ Edit ] [ Delete ] 1#

对所有的数进行预处理,unique , 每一个数字 在查询的时候都有一个存在区间,每一次 update直接就更新该数字的存在区间,然后 用一个数据结构 计数 (删除 区间,该区间的counter-1,插入区间 该区间的counter+1)

应该没有问题吧。。
貌似是 O(N*LOG(N))的
save_code @ 2017-12-04 08:52:28
[ Quote ] [ Edit ] [ Delete ] 2#
恩,对应插入的区间的数字 也要跟着删除
save_code @ 2017-12-04 14:58:22
[ Quote ] [ Edit ] [ Delete ] 3#
恩 N*LOG(N)果然是错的,然后 如果记录 每个数字的不存在区间, 不存在区间完全覆盖查询的区间,那么 answer++,感觉要用K-Dtree 或者二维树状数组离散化之类的数据结构,好纠结
save_code @ 2017-12-04 14:59:15
[ Quote ] [ Edit ] [ Delete ] 4#
是 answer-- 总数减去 不存在个数
save_code @ 2017-12-04 20:27:43
[ Quote ] [ Edit ] [ Delete ] 5#
今天下午查了一下 K-D tree查询矩形的复杂度最坏是 O(N^1.5)的

这道题 应该也可以用二维数状数组 离散化,记得CF 上Zlobober讲过一个 O(N*LOG(N)^2)的树状数组离散化,现在找不到了
nzhtl1477 @ 2017-12-04 21:08:03
[ Quote ] [ Edit ] [ Delete ] 6#
树状数组的高维离散化是树套树功能的子集吧。。。
nzhtl1477 @ 2017-12-04 21:10:05
[ Quote ] [ Edit ] [ Delete ] 7#
我把题号看错了。。
save_code @ 2017-12-04 21:10:38
[ Quote ] [ Edit ] [ Delete ] 8#
对了 这道题貌似 也可以CDQ分治啊, 然后可以 压缩区间 扫描线,好像也是O(Q*LOG(q)*log(N))的
nzhtl1477 @ 2017-12-04 21:10:51
[ Quote ] [ Edit ] [ Delete ] 9#
这个题可以证明下界是nlog^2n的吧
nzhtl1477 @ 2017-12-04 21:11:15
[ Quote ] [ Edit ] [ Delete ] 10#
可以分治的
save_code @ 2017-12-04 21:11:36
[ Quote ] [ Edit ] [ Delete ] 11#
你是说KDTREE的下界?
nzhtl1477 @ 2017-12-04 21:11:51
[ Quote ] [ Edit ] [ Delete ] 12#
不是。。
nzhtl1477 @ 2017-12-04 21:12:15
[ Quote ] [ Edit ] [ Delete ] 13#
因为这个题是带修改区间不同数个数的严格加强版
nzhtl1477 @ 2017-12-04 21:12:36
[ Quote ] [ Edit ] [ Delete ] 14#
而那个似乎只能做到nlog^2n?
nzhtl1477 @ 2017-12-04 21:12:54
[ Quote ] [ Edit ] [ Delete ] 15#
等等可能可以除掉一两个loglogn
nzhtl1477 @ 2017-12-04 21:12:59
[ Quote ] [ Edit ] [ Delete ] 16#
不过我不会。。
save_code @ 2017-12-04 21:15:12
[ Quote ] [ Edit ] [ Delete ] 17#
没有修改的话 可以 排序+扫描线+树状数组吧
save_code @ 2017-12-04 21:15:43
[ Quote ] [ Edit ] [ Delete ] 18#
修改的话 可以考虑套个CDQ分治
nzhtl1477 @ 2017-12-04 21:15:43
[ Quote ] [ Edit ] [ Delete ] 19#
当然可以。。
save_code @ 2017-12-04 21:16:12
[ Quote ] [ Edit ] [ Delete ] 20#
也可以考虑 N^1.5 的 KDTREE
nzhtl1477 @ 2017-12-04 21:16:53
[ Quote ] [ Edit ] [ Delete ] 21#
KDT查询矩形据说很慢
不知道会不会TLE了
save_code @ 2017-12-04 21:17:43
[ Quote ] [ Edit ] [ Delete ] 22#
我看到一篇BLOG 介绍 说是 N^1.5的,我也没有试过 实际效果
不过 感觉分治的话 常数有点大啊
nzhtl1477 @ 2017-12-04 21:18:03
[ Quote ] [ Edit ] [ Delete ] 23#
分治非常的快
save_code @ 2017-12-04 21:18:59
[ Quote ] [ Edit ] [ Delete ] 24#
恩, LOG级的感觉总该比 根号的 要好点吧
nzhtl1477 @ 2017-12-04 21:19:07
[ Quote ] [ Edit ] [ Delete ] 25#
是吧
nzhtl1477 @ 2017-12-04 21:19:19
[ Quote ] [ Edit ] [ Delete ] 26#
所以您要不要写写这个题啊~
save_code @ 2017-12-04 21:20:17
[ Quote ] [ Edit ] [ Delete ] 27#
有时间了再写吧 我还忙着在ural oj 刷rating呢
save_code @ 2017-12-04 21:20:38
[ Quote ] [ Edit ] [ Delete ] 28#
100题 56W +rating,哈哈,记录啊
nzhtl1477 @ 2017-12-04 21:20:59
[ Quote ] [ Edit ] [ Delete ] 29#
orz
save_code @ 2017-12-04 21:21:02
[ Quote ] [ Edit ] [ Delete ] 30#
可惜 还差 两道 1589+1394
nzhtl1477 @ 2017-12-04 21:22:23
[ Quote ] [ Edit ] [ Delete ] 31#
orz
save_code @ 2017-12-04 23:47:51
[ Quote ] [ Edit ] [ Delete ] 32#
继续刷水题也没有意义,准备 开工,手动二分 把1394 TEST 70 搞出来
nzhtl1477 @ 2017-12-05 10:19:54
[ Quote ] [ Edit ] [ Delete ] 33#
orz
save_code @ 2017-12-05 10:36:32
[ Quote ] [ Edit ] [ Delete ] 34#
晕死 test 70 正向序就能 搜出来,我参数调小了啊,现在已经到了 test 77了,这个CASE 卡了我3年啊
save_code @ 2017-12-05 10:36:54
[ Quote ] [ Edit ] [ Delete ] 35#
NOD,NOD,, too young too naive
save_code @ 2017-12-05 10:37:27
[ Quote ] [ Edit ] [ Delete ] 36#
2011 年之前就应该可以AC的。。。
save_code @ 2017-12-05 10:37:58
[ Quote ] [ Edit ] [ Delete ] 37#
哦是 2014年
LZSB111 @ 2017-12-07 09:04:56
[ Quote ] [ Edit ] [ Delete ] 38#
这不是谁给玲珑杯出的题么?
save_code @ 2018-01-03 19:42:22
[ Quote ] [ Edit ] [ Delete ] 39#
没有错
[Top] [Previous Page] [Next Page]

HOME Back