「HEOI2012」采花

传送门

Taduro 的题解

sto Taduro orz

首先，读完题一定有人要跳出来喊「莫队！」。

莫队！

然后再一看数据范围

对于 $100\%$ 的数据，$1\leqslant c\leqslant n,m\leqslant 2\times 10^{6}$。

笑容逐渐消失。

然后根据数据范围，我们不难猜出正解是树状数组。然后问题来了，树状数组什么时候有这种操作了。

首先这个样例比较菜，我们手造一个：

1 6 2 4 2 3 6 2

首先我们维护一个 nxt 数组，表示当前颜色下一次出现的位置，不存在的话就是 $0$。上面的样例对应的 nxt 差不多长这样：

i	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
c[i]	$1$	$6$	$2$	$4$	$2$	$3$	$6$	$2$
nxt[i]	$0$	$7$	$5$	$0$	$8$	$0$	$0$	$0$

然后我们把所有询问离线下来，以左端点为第一关键字，右端点为第二关键字排一下序。维护一个指针，让它一直跟着当前询问的左端点走。一开始它在 $1$。

然后我们还需要一个数组 ans，对于每一种颜色，我们令其在指针所在位置及其之后的部分中第二次出现的位置的 ans 为 $1$。

i	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
c[i]	$1$	$6$	$2$	$4$	$2$	$3$	$6$	$2$
ans[i]	$0$	$0$	$0$	$0$	$1$	$0$	$1$	$0$

因为一种颜色第一次出现不会被统计，第二次出现才会被统计，在这之后就算再出现也不会多统计了。

不难发现，此时 $\sum_{i=1}^{x}ans[i]$ 就是询问 1 x 的答案。

需要移动指针时，我们每次只移动一个位置。移动完之后，移动前指针所在位置的颜色第二次出现的位置就变成了第一次出现，因此我们需要将这个位置上的 ans 置为 $0$。同理，第三次就变成了第二次，因此我们需要将其置为 $1$。因为我们每次只移动一个位置，所以说只有一个颜色的状态会发生变化。

这个时候 nxt 数组就派上用场了，我们可以通过它块速地定位到当前颜色后面的出现位置。

让我们以上面的样例为例，稍微模拟一下指针的移动（下划线表示指针当前位置）：

i	$\underline{1}$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
c[i]	$1$	$6$	$2$	$4$	$2$	$3$	$6$	$2$
ans[i]	$0$	$0$	$0$	$0$	$1$	$0$	$1$	$0$

i	$1$	$\underline{2}$	$3$	$4$	$5$	$6$	$7$	$8$
c[i]	$1$	$6$	$2$	$4$	$2$	$3$	$6$	$2$
ans[i]	$0$	$0$	$0$	$0$	$1$	$0$	$1$	$0$

i	$1$	$2$	$\underline{3}$	$4$	$5$	$6$	$7$	$8$
c[i]	$1$	${\color{red}6}$	$2$	$4$	$2$	$3$	${\color{red}6}$	$2$
ans[i]	$0$	$0$	$0$	$0$	$1$	$0$	${\color{red}0}$	$0$

i	$1$	$2$	$3$	$\underline{4}$	$5$	$6$	$7$	$8$
c[i]	$1$	$6$	${\color{red}2}$	$4$	${\color{red}2}$	$3$	$6$	${\color{red}2}$
ans[i]	$0$	$0$	$0$	$0$	${\color{red}0}$	$0$	$0$	${\color{red}1}$

对于一次询问 l r，我们将指针移动到 l 这个位置之后查询 $\sum_{i=l}^{r}ans[i]$ 即可。

代码就不贴了，其实我还没写（