题目链接:249. 蒲公英 算法分析 进阶指南上算法描述已经很清晰了。这里是用vector维护的每个数在序列中出现的下标。假设总共T块,预处理出每两个块之间的最小众数,需要时间O(nT)。m个查询小块内每个数的出现次数为O(mn/T*logn),总体时间复杂度为两者之和。 根据均值不等式,如果时间复杂度最低,应满足 n T = m n / T l o g n nT=mn/Tlogn nT=m
Description Input 修正一下 l = (l_0 + x - 1) mod n + 1, r = (r_0 + x - 1) mod n + 1 Output Sample Input 6 3 1 2 3 2 1 2 1 5 3 6 1 5 Sample Output 1 2 1 HINT 修正下: n <= 40000, m <=
题目大意: 题目链接:https://www.luogu.org/problemnew/show/P4168 给出一个长度为 n n n的序列, m m m次询问,求区间 [ l , r ] [l,r] [l,r]中的众数。强制在线。 思路: 以下内容参考 l y d lyd lyd《算法竞赛进阶指南》。 先离散化不解释。 分块算法一般都是以“暴力+区间预处理+暴力”的方法做的。