LuoguP5356 [Ynoi2017] 由乃打扑克

Description

题目链接:P5356

一个长为 $n$ 的序列 $a$,需要支持 $m$ 次操作,操作有两种:

  1. 查询区间 $[l,r]$ 的第 $k$ 小值。
  2. 区间 $[l,r]$ 加上 $k$。

$1\leq n,m\leq 10^5,-2\times 10^4\leq$ 每次加上的数和原序列的数 $\leq 2\times 10^4$。

Solution

查询第 $k$ 小,直接想到两种方法:

  1. 二分枚举然后再统计次数统计,复杂度 $O(\sqrt{N}log_2V)$
  2. 值域分块,记录前缀和。

第一种方法显然

很遗憾,被我卡掉了。——lxl

但是却可以AC本题

考虑第二种方法区间修改有点困难,所以直接上第一种方法,修改时只要整块打上标记,散块暴力修改即可,加上各种优化:

  1. 二分的边界可以先跑一次求出最大最小值。
  2. 二分判断统计时,最大值也小于等于 $mid$,直接加上块长即可,最小值大于 $mid$,直接跳过即可。
  3. 一颗沉稳的心

Code

暂无评论

发送评论 编辑评论


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