comet OJ 公众号
comet OJ 用户群
题目链接
出题人
$\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}$