LuoguP4119 [Ynoi2018] 未来日记

Description

题目链接:P4119

一个长为 $n$ 的序列 $a$,有 $m$ 次操作。

  1. 把区间 $[l,r]$ 内所有的 $x$ 变成 $y$。
  2. 查询区间 $[l,r]$ 内第 $k$ 小值。

$1\leq n,m,a_i\leq 10^5$

Solution

stO 陈指导 Orz,陈指导码了一个下午就做完了,蒟蒻我竟然写了3天。

首先要对序列分块,对于整块,考虑直接把一种数字直接改成另一种数字,然后可以考虑使用并查集。对于散块,我们可以直接暴力枚举修改,暴力重构并查集即可。

这时候需要分类讨论:

  1. 该块中没有出现 $x$,那么直接跳过即可。
  2. 该块出现了 $x$,没有出现 $y$,那么就直接用并查集映射即可。
  3. 该块出现了 $x$,也出现了 $y$,直接暴力重构。

然后我们会发现一个细节:如果我们并查集记录的是每个块的颜色指向的真实颜色,那么会出现一些问题:如果将块内所有 $1$ 改为 $2$,再将所有 $3$ 改为 $1$ 这种情况就非常难处理。

所以我们可以选择记录块内每个位置在块内与其数字相同的编号最小值,这样就可以完美规避上面的问题了。

然后我们发现询问还是有点苦难,这时候应该可以想到查找区间第 $k$ 小的常见套路:值域分块,记录每个序列块的前缀和。具体实现方法就是”带插入区间第 $k$ 小”方法。

这时候敲代码的时候又会发现一个问题:每次修改要更新的是前缀和,复杂度会升到 $O(NM)$。考虑修改的过程中开个桶记录下第 $k$ 个块修改的权值和,修改全部完成后再扫一遍所有的块,更新前缀和即可。

可以发现暴力重构块的次数是有限的,每次合并时块内权值种类会减少 $1$,而权值种类总共不会超过$n+m$,可以保证复杂度正确性 $O((N+M)\sqrt{N})$。

然后不知道为什么被lxl卡得很慢

Code

暂无评论

发送评论 编辑评论


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