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 2038 >> 这题有没有比莫队更快的做法
wjy666 @ 2018-01-20 16:30:28
[ Quote ] [ Edit ] [ Delete ] 1#
RT,感谢各位大佬
nzhtl1477 @ 2018-01-20 16:31:15
[ Quote ] [ Edit ] [ Delete ] 2#
如果有的话
就有趣了
maoxiangui @ 2018-05-31 18:51:03
[ Quote ] [ Edit ] [ Delete ] 3#
lxl!
stdio @ 2018-06-10 09:25:23
[ Quote ] [ Edit ] [ Delete ] 4#
有卡常莫队
nzhtl1477 @ 2018-06-10 19:30:49
[ Quote ] [ Edit ] [ Delete ] 5#
卡常莫队还不是莫队
save_code @ 2018-06-13 20:13:26
[ Quote ] [ Edit ] [ Delete ] 6#
可以不用莫队,有这么一种做法 枚举 个数 >=sqrt(n)的 颜色然后 暴力 计数N*SQRT(N)
对于 个数 <=sqrt(n)的 所有颜色 ,枚举 所有的两两相同元素 对 一共 N*SQRT(N)对,然后 和区间一起 扫描线,离散化 +树状数组 统计 区间内的相同颜色对 有多少个
这个是N*SQRT(N*LOG(n)) 比莫队略差点
nzhtl1477 @ 2018-06-13 22:58:57
[ Quote ] [ Edit ] [ Delete ] 7#
和莫队差不多吧,只是莫队是对序列的根号平衡,这个是对值的根号平衡
save_code @ 2018-06-13 23:11:07
[ Quote ] [ Edit ] [ Delete ] 8#
感觉做法还是不一样的吧, 虽然都是 根号
nzhtl1477 @ 2018-06-13 23:55:14
[ Quote ] [ Edit ] [ Delete ] 9#
诶好奇怪为什么会不一样呢
nzhtl1477 @ 2018-06-13 23:58:01
[ Quote ] [ Edit ] [ Delete ] 10#
等等这个好像不成立
nzhtl1477 @ 2018-06-13 23:58:20
[ Quote ] [ Edit ] [ Delete ] 11#
为什么可以 离散化+树状数组 啊
nzhtl1477 @ 2018-06-13 23:58:35
[ Quote ] [ Edit ] [ Delete ] 12#
我怎么感觉只能树套树
nzhtl1477 @ 2018-06-13 23:59:11
[ Quote ] [ Edit ] [ Delete ] 13#
nsqrtn个二维平面点,每次查的是一个矩形数点?
save_code @ 2018-06-14 00:11:37
[ Quote ] [ Edit ] [ Delete ] 14#
查询的区间 要包含 这个 二维点对啊, 为什么不能离散化+树状数组
save_code @ 2018-06-14 13:06:26
[ Quote ] [ Edit ] [ Delete ] 15#
我笨啊维护一个前缀和就行了,不带log
save_code @ 2018-06-14 13:09:46
[ Quote ] [ Edit ] [ Delete ] 16#
而且这个算法支持修改等复杂操作以后我们可以不用莫队了
iloi @ 2018-06-14 13:45:58
[ Quote ] [ Edit ] [ Delete ] 17#
orz save_code!
nzhtl1477 @ 2018-06-14 16:18:08
[ Quote ] [ Edit ] [ Delete ] 18#
也就是说每个位置可能有sqrtn个数,每次查询位置区间[l,r]内值在[l,r]的个数?
nzhtl1477 @ 2018-06-14 16:18:57
[ Quote ] [ Edit ] [ Delete ] 19#
然后差分,然后用一个O( 1 )修改O( sqrtn )查询的分块来维护吗
nzhtl1477 @ 2018-06-14 16:19:11
[ Quote ] [ Edit ] [ Delete ] 20#
如果是这样的话,复杂度是O( nsqrtm + msqrtn ),劣于莫队
save_code @ 2018-06-14 16:21:43
[ Quote ] [ Edit ] [ Delete ] 21#
咦待修改的莫队不是N^5/3吗?
nzhtl1477 @ 2018-06-14 16:50:15
[ Quote ] [ Edit ] [ Delete ] 22#
这个题为什么是带修改的莫队啊
maoxiangui @ 2018-06-16 19:25:52
[ Quote ] [ Edit ] [ Delete ] 23#
毒瘤lxl!!!
2016gdgzoi471 @ 2018-07-08 15:10:12
[ Quote ] [ Edit ] [ Delete ] 24#
毒瘤lxl!!!
strangers @ 2018-07-08 19:55:43
[ Quote ] [ Edit ] [ Delete ] 25#
毒瘤lxl!!!
wangyuchen @ 2018-07-19 16:22:49
[ Quote ] [ Edit ] [ Delete ] 26#
毒瘤lxl!!!
cnlarryzhong @ 2018-07-24 10:26:19
[ Quote ] [ Edit ] [ Delete ] 27#
毒瘤lxl!!!
rilisoft @ 2018-07-24 11:57:37
[ Quote ] [ Edit ] [ Delete ] 28#
毒瘤lxl!!!
alpha1022 @ 2018-08-13 11:08:22
[ Quote ] [ Edit ] [ Delete ] 29#
毒瘤lxl!!!
QuartZ_Z @ 2018-08-13 20:54:54
[ Quote ] [ Edit ] [ Delete ] 30#
毒瘤lxl!!!
yyb @ 2018-08-15 21:27:57
[ Quote ] [ Edit ] [ Delete ] 31#
勇石博士没有弱点!!!!
wjy666 @ 2018-08-16 15:38:51
[ Quote ] [ Edit ] [ Delete ] 32#
orzyyb!!!
wjy666 @ 2018-08-16 15:40:21
[ Quote ] [ Edit ] [ Delete ] 33#
出来跟lxl学分块
siyuan @ 2018-12-03 22:33:27
[ Quote ] [ Edit ] [ Delete ] 34#
毒瘤lxl!!!
[Top] [Previous Page] [Next Page]

HOME Back