LuoguP4168 [Violet]蒲公英

Description

题目链接:P4168

给定一个长度为 $n$ 的序列,$m$ 次询问,每次询问输出区间众数,如果出现次数相同,输出编号小的。

强制在线

$1\leq n\leq 4\times 10^4,1\leq m \leq 5\times 10^4,1\leq a_i\leq 10^9$

Solution

看到区间众数,自然而然就想到可以直接分块,时间复杂度 $O((N+M)\sqrt{N})$,空间复杂度 $O(N\sqrt{N})$,足矣通过此题,由于其他题解都写得很详细,这里就不再赘述。

那有没有更加优秀的算法呢?当然有,可以仿照P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III的思路,预处理出 $[i,j]$ 块的众数出现次数,用 vector 按顺序存储每个数的所有元素出现位置,记录对应下标,每次询问的时候整块直接用预处理中的即可,散块个数最多为 $2\sqrt{N}$ 个,所以最多使答案增加 $2\sqrt{N}$,所以我们只需要扫一遍,判断这些数的出现个数是否能使答案加一即可。

总时间复杂度 $O((N+M)\sqrt{N})$,空间复杂度 $O(N)$,然而这种做法常数更小,所以跑得飞快,顺手卡一卡就拿到了最优解

Code

普通分块:

第二种做法:

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇