Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:莫队算法+线段树!复杂度(n + q)sqrt(n)*log(n),可以是无序序列,可惜TLE。。

Posted by test_solution at 2014-07-31 16:50:01 on Problem 3368 and last updated at 2014-07-31 16:50:26
In Reply To:Re:莫队算法+线段树!复杂度(n + q)sqrt(n)*log(n),可以是无序序列,可惜TLE。。 Posted by:test_solution at 2014-07-31 16:27:24
> 虽然不知道莫队算法是神马,但是 我觉得你的代码 有问题:
> 
> q[i].block根本就没有用上(排序是对q[i].block排的但是本质还是对q[i].l排序,
> 
> q[i].block=q[i].l/BLOCK, BLOCK是个constant),也就是说你的整个算法跟BLOCK==
> sqrt(n)无关,估计也就是O(n*q*log())了。。。。


倒是根据你的复杂度提示蛋疼出了一个 (n+q)*sqrt(n)*log(n)的搞法(加强版),可
能比较复杂,比较暴力,暂时没想到简单的:

将q个区间拆成O(q)个小区间,疑似是 2*q,  对每个小区间维护一个块状链表  然后
对询问的区间排序, 按照顺序,将小区间所在的块状链表合并或者删除(块状链表的每一块都是增序的,并且需要知道这一块的最大频率的数,以及头尾数字的频率),
查询的时候暴力比较每个块的最大频率以及 头尾相同数字相接的 频率和进行比较,取最大值,不知道有木有简单点的办法。。。 


至于这道题原题 序列是增序的,貌似可以蛋疼出O(n+q)的,类似区间最大值的单调队列求法。。。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator