LuoguP3793 由乃救爷爷

Description

题目链接:P3793

给定一个 $n$ 个数的序列,有 $m$ 个询问,每次询问区间最大值。

$1\leq n,m\leq 2\times 10^7$,保证数据随机。

Solution

考虑分块。

如果朴素分块肯定是不能过的 $O(N\sqrt{N})$,但是这题并没有修改操作,所以考虑先预处理出第 $l$ 个块到第 $r$ 个块的最大值、第 $i$ 个块的前缀最大值、第 $i$ 个块的后缀最大值。

每次询问的时候如果 $l,r$ 在同一个块内可以直接暴力,出现此情况应该是 $\frac{1}{\sqrt{N}}$,而单次暴力复杂度为 $O(\sqrt{N})$,所以总期望复杂度是 $O(N)$。

如果不在同一块内直接利用预处理出的结果 $O(1)$ 即可。

所以总的时间复杂度是 $O(N)$。

Code

暂无评论

发送评论 编辑评论


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