第二道 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 |
|