第二道 ynoi ……前前后后不知道写了多久。
Idea:fdy Solution:fdy&lxl Std:lxl&csy Data:lxl
“望月悲叹的最初分块” (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))
这个是这个系列中第一个被出出来的题,当时给了多校(然后的确没人做出来耶),然后被搬到了毛营(然后还是没人做出来耶)
这个是我同学出的,不是我出的(当时问我我也不会这题来着),来源似乎是有个 cdqz 高新校区的小朋友看错了一个 cf 题,然后被加强造出来的
这里就直接挂csy的题解了,和我的不太一样,但是大概思路还是差不多的,我的做法是和T1有点类似的维护方法
对这题的评价:8.5/11
—— lxl 博客
bzoj怎么挂了
我是不是什么时候也该去看看未来日记
题意简述
给定一个长 $n$ 的整数序列, $1\le n,m,a_i\le 100000$ , $m$ 个操作,操作包括:
- 把区间 $[l,r]$ 中所有 $x$ 变为 $y$ ;
- 查询区间 $[l,r]$ 中的第 $k$ 小值。
没强制在线,然而好像并没有离线做法。
主要思路
首先先分块,对序列与值域都分块。以下均在块长 $O(\sqrt{n})$ 下讨论。
分块无修区间第 k 大
先考虑怎么分块做无修区间第 $k$ 大。可以维护两个数组 $C[val][d]$ 表示前 $d$ 块中值为 $val$ 的数的个数, $B[valid][d]$ 表示前 $d$ 块中值在第 $valid$ 个值域块里的数的个数。
询问时维护两个临时数组 $tc[val]$ 与 $tb[valid]$ ,用来处理零碎块的贡献。
然后枚举答案位于哪一个值域块,再在这一个块里暴力枚举答案就可以 $O(\sqrt{n})$ 求出区间第 $k$ 大。
维护修改操作
如何实现将 $[l,r]$ 中 $x$ 变为 $y$ 的操作?
发现 $x$ 变为 $y$ 的操作类似并查集。维护数组 $rt[val][d]$ 表示第 $d$ 块中某个为 $val$ 的数的位置(即任意时刻保证 $a[\ rt[val][d]\ ] = val$ ,若块中无 $val$ 则将 $rt[val][d]$ 设为 $0$)。
再维护并查集数组与函数 $fth[id],find(id)$ ,将第 $d$ 块的值为 $val$ 的数挂到 $rt[val][d]$ 子树上。
此时再来考虑如何实现修改操作。
对于散块,直接将 $x$ 与 $y$ 两棵子树重置。
对于整块 $bid$ :
- 如果没有 $x$ ,直接跳了;
- 如果没有 $y$ ,把 $rt[y][bid]$ 设为 $rt[x][bid]$;
- 如果有 $y$ ,把 $fth[\ rt[x][bid]\ ]$ 设为 $rt[y][bid]$。
最后把$a[\ rt[x][bid]\ ]$ 设为 $y$ ,把 $rt[x][bid]$ 设为 $0$ ,大概想一下应该可以知道为什么。
还要修改 $C[val][d]$ 与 $B[valid][d]$ ,由于只涉及 $x$ 与 $y$ 这两个值,所以暴力修改这两个数组完全可以承受。
最后修改的时间复杂度就是 $O(\sqrt{n})$ 。
参考代码
内存限制 $\text{500MB}$ ,所以块长不能取 $O(\sqrt{n})$ (会爆空间),要稍微开大一点。
记得判 $x$ 与 $y$ 相等的情况,如果不判会莫名挂。
更多细节参考代码。
至于函数名称和大常数就不要在意了……
1 |
|