CF351D Jeff and Removing Periods

题意理解:

有一段数列 \(a_1\) ~ \(a_n\) , 不同数字代表不同颜色 。共 \(q\) 次询问,每次询问为:

在 l 到 r 之间每次可以先选定一个颜色 \(k\) , 然后删除 位置 形成 等差数列 且颜色为 \(k\) 的一组点。删除一次后可重排序列,问最少多少次可以删除完整个序列。

题意转换:

不难发现,删除第一次后的重排,我们可以让相同的数字相邻,这样所有相同的数字都构成一个等差序列(公差为1)。如此我们就可以用区间内 总颜色数 删除完整个序列。(记颜色数为 \(color\))

所以我们现在只需要考虑,第一次删除的时候是否存在颜色 \(m\) , 使我们一次就可以将该区间内的所有 \(m\) 删除。如果可以,则 \(ans = color\) ,否则为 \(color + 1\)。

Solution

Step 1:

这样的思路转换可以让我们想到两道题:

莫队 数颜色 和 树状数组 HH的项链

这里我们用树状数组的思路介绍一下这题的做法。

Step 2:

先考虑较为好想的 “区间内 总颜色数” 。

根据经验,我们将查询按右端点为关键字从小到大排序,离线处理:

遍历 \(i = 1\) ... \(max(r_i)\)

如果第 \(i\) 位颜色为 \(k\) , 则将前一个颜色为 \(k\) 的位置 \(-1\) ,再将这个位置 \(+1\) 。最后用树状数组求 l 到 r 的区间和即可。

简要说明这个做法为什么是对的:

因为我们将右端点离线处理,所以颜色为 \(k\) 只有最右的位置对答案有所贡献,而其余的颜色为 \(k\) 的点贡献为 \(0\) 。所以我们每次更新一个颜色 \(k\) 的右端点时,将该位置贡献 \(+1\) ,而将上一个颜色为 \(k\) 位置贡献 \(-1\) 。

Step 3:

再考虑如何判断 l 到 r 的区间之间是否存在一种颜色其位置形成等差数列。

一个巧妙地想法:

预处理出两个数组。

\(nxt[i]\) 表示前一个 \(a_i\) 出现在什么位置

\(del[i]\) 表示如果询问的 \(l <= del[i]\) ,则 \([l,r]\) 内与 \(a_i\) 相同的数不可能被一次性删除。

现在我们开另一个树状数组,\(sum(l , r)\) 代表 l 到 r 之间有多少个颜色的位置不符合等差数列。

遍历 \(i = 1\) ... \(max(r_i)\)

如果第 \(i\) 位颜色为 \(k\) , 则将 \(del[nxt[i]]\) 位置 \(-1\) ,再将 \(del[i]\) 位置 \(+1\) 。最后用树状数组求 l 到 r 的区间和即可。

说明和 Step 2 很类似。因为我们将右端点离线处理,所以颜色为 \(k\) 只有 \(del[i]\) 位置对答案有所贡献,而其余的颜色为 \(k\) 的点贡献为 \(0\) 。

现在我们只需要知道 \(sum_1(l , r)\) 是否等于 \(sum_2(l , r)\) 即可,若相等说明没有任一颜色存在等差数列,则将答案+1,否则答案不变。

然后这题就被愉快的A掉啦!!!

Code

总结:

出现 “区间内有多少种不同颜色”此类表述时,可以选择按右端点从小到大排序离线处理。同一颜色留下对答案有贡献的一个位置设为 1 即可 ,该点及右边区间答案都受影响,左边都不受影响。

上一篇:ios 常用命令封装


下一篇:0x06 倍增