Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Re:此题有O(q+mlogm)的算法（设序列中不同值的个数为m）

Posted by zhangk at 2012-01-25 21:16:34 on Problem 3368
In Reply To:此题有O(q+mlogm)的算法（设序列中不同值的个数为m） Posted by:mike_nzk at 2009-04-04 20:26:44

> 每次询问不需要O(logn)复杂度。
> 只要从小到大记录这个序列每个值的起始位置、结束位置和频数（即离散化），对频数进行rmq即可，每次询问只用O(1)的复杂度，300多ms就可以过了。
空间上不行吧

Followed by:

Post your reply here: