题目链接

C.序列

出题人

$\color{orange}{Ynoi}$

题解

定义$f_x$表示所有序列中，存在极大连续段右端点为$x$的序列个数

我们知道如果一个序列$a$有$x = n或a_x \not= a_{x+1}$，则会对$f_x$产生$1$的贡献

由于每次操作我们复制后，对$l$到$r$赋值一个新的数

所以所有序列下标为$r$的值一定和下标为$r+1$的值不同，所以此时$f_r = f_r(复制后不操作)+2^{i-1}(所有复制后都操作的序列)$

同理, 下标$l-1$的值和下标$l$的值不同，所以$f_{l-1} = f_{l-1}+2^{i-1}$

对于所有$l \leq x <r$,此时由于$l$~$r$被赋了同样的值，所以此时操作后的序列都不对$f_x$ 产生贡献,所以此时$f_x$只有复制后没有操作的部分，$f_x = f_{x}$

对于所有$x <l-1或x >r$,是否执行赋值操作对$f_x$没有影响，由于被复制了两份，$f_x = 2f_{x}$

AC 代码参考