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

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

$1\leqslant l\leqslant r\leqslant n,1\leqslant a_i,x\leqslant 100000$


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

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

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

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

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

然后就考虑怎么维护。

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

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

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

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

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

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

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

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

最后修改:2020 年 11 月 01 日 09 : 41 PM