维护一个 $n$ 个元素的序列 $a_1,a_2,\dots,a_n$,有 $m$ 次操作,分为如下两种。

  • 给定 $l,r,x$ ,将$a_l,a_{l+1},\dots,a_r$ 中所有大于 $x$ 的元素减去 $x$;
  • 给定 $l,r,x$,询问 $a_l,a_{l+1},\dots,a_r$ 中,有多少个元素恰好等于 $x$。

$1\leq n,m\leq 10^5$,$1\leq l\leq r\leq n$,$1\leq a_i,x\leq 10^5$。


第一道 Ynoi 题纪念(指对照 std 编程 $2$ 天发现数组两维开反了

发现是一道非常妙的分块题呢。

看到 $n,m$ 第一眼以为是 $O(n\log n)$ 的数据结构题,然后发现根本不可做(bushi

然后想了想能不能用大概是 $O(n\sqrt n)$ 的分块过去。

然后可以惊奇的发现还有一个数据特性让我们可以方便分块:$a_i\leq 10^5$,也就是说值域是在 $1e5$ 这样的一个级别,块数是根号级别也就是在三百多的一个级别,可以考虑对每一块记录每个值的出现次数,这样做的空间复杂度是 $O(n\sqrt n)$。

然后就考虑怎么维护。

考虑对每个块里的每个值选择一个代表,我们要修改 这个值 的话这些所有这个值的都要修改。于是这里我们可以用并查集来做到,我们把相同值的用并查集连在一起,并查集是 $O(\alpha(n))$ 的,可以当做常数忽略掉,下面默认都忽略这一项。

这样对于每一个 d[块编号][数值],维护 $f$ (第一个该数值对应的位置),$cnt$(块内该数值出现的次数)。在 $x$ 块内合并值 $a$ 至值 $b$,就访问 d[x][a]d[x][b] 直接贴上去就好了。

然后假设块内最大值是 $v$,要减去的是 $x$,每次我们如果暴力的话需要把 $[x+1,v]$ 合并到 $[1,v-x]$,显然时间复杂度是 $O(v-x)$ 的,但是毕竟是 Ynoi 的题,这样肯定是过不了的。考虑如何优化。

发现把大于 $x$ 的数减去 $x$ 的操作,就等同于把块内所有数先减去 $x$,再对小于 $x$ 的数全部加上 $x$ 。这样的时间复杂度是 $O(x)$。

然后考虑维护块内最大值 $v$,当 $2x\ge v$ 的时候,我们就用第一种暴力操作来合并,否则我们就用后面一种操作来,但是这个所有数减去 $x$ 的操作肯定不会暴力做的,于是还考虑添加一个懒标记 $tag$ 代表需要减去的数。每次需要用到这些值的时候就可以 $down$ 来下传标记啥的..

对于零散的边角,我们可以直接推散重构,可以写一个 init 来重构一个块。

然后就没什么细节了。。主要就是那个部分的减法转换成部分的加法加全局的减法,想到这个应该就能理解代码了。。

代码就不放了,以后有空再来打一遍吧..

最后修改:2021 年 08 月 15 日
如果觉得我的文章对你有用,请随意赞赏