写了有一段时间了,忘更博客(咕咕咕)。
Idea:lxl Solution:lxl Std:lxl Data:lxlIdea:lxl Solution:lxl Std:lxl Data:lxl
“突刺贯穿的第二分块” (妈呀这名字好中二啊(谁叫我要用日本轻小说中的东西命名真是作死))
这题的来源比较神奇,大概是 csy 搬了一个全局大于 x 的减 x,查 kth 什么的题,然后我想把这个出区间上
然后直接出会得到一个 $O(n\sqrt{n}\log n)$ 的废物,当时想了很久都没想到什么trick能做值域1e9的情况(有没有人教教我啊)
然后改了改发现值域1e5是可以做的就出了出来
对这题的评价:6/11
顺便这题的 Version4 是查询区间 rank ,我记得当时我用当时感觉挺厉害的 trick 做到了和现在一样的复杂度不过感觉不 practical 所以没有挂出来
所以 lxl 啥时候把加强的数据咕出来啊(
好现在咕出来了,然后我过不去了,找时间来改(咕咕咕
题意简述
一个长为 $n$ 的序列,$m$ 个操作。操作可能是以下两种:
- 将区间 $[l, r]$ 内所有大于 $x$ 的数减去 $x$ 。
- 求区间 $[l, r]$ 内 $x$ 的个数。
$1\le n, m, a_i\le 10^5$ 。
主要思路
考虑分块,块长 $O(\sqrt{n})$。显然,每块的最大值总是不增的。
我们用某种数据结构来维护块内的所有数,设将某个数合并到另一个数上的时间复杂度是 $O(k)$,查询某种数的个数的时间复杂度是 $O(t)$。
假设一个块所有大于 $x$ 的数减去 $x$ ,最大值为 $v$ 。
- 当 $v \le 2\times x$ 时,可以把所有 $[x + 1, v]$ 内的数合并到 $[1, x]$ 上。这样,我们用 $O(v - x)\times O(k)$ 的时间让块内的最大值减小了 $v - x$ 。
- 当 $v > 2\times x$ 时,可以把所有 $[1, x]$ 内的数合并到 $[x + 1, 2\times x]$ 上。这样,我们用 $O(x)\times O(k)$ 的时间让块内的最大值减少了 $x$ 。
散块的修改则重构整块,复杂度 $O(k\times\sqrt{n})$。
由于开始时所有块的最大值之和是 $O(n\sqrt{n})$ ,所以修改的复杂度是 $O(n\sqrt{n}\times k)$ 。查询的复杂度是 $O(n\sqrt{n}\times t)$ 。
类似未来日记,使用并查集来维护块内的所有数,则 $k = t = 1$ ,总复杂度 $O(n\sqrt{n})$ ,可以通过此题。
参考代码
1 |
|
参考资料
据说询问区间某个数的 rank 也可做?然而我太弱了并不会