题解 CF1102E 【Monotonic Renumeration】

这题还是需要思考一会的。

$1.$初步思路

首先，由第三个条件$b_{i+1}=b_i$或$b_{i+1}=b_i+1$，我们可以知道：$b_{i+1}\geqslant b_i$

所以，这个数列一定是升序排列的！

再回过头来看第二个条件：如果$a_i=a_j$，则$b_i=b_j$。

那么，在一个升序排列的数列中，有两个数相等，会发生什么呢？这两个数之间的所有数都相等！

假设$b_i,b_j$之间有一个数$b_k$不与它们相等。

那么，如果$b_k>b_i$，又因为$b_i=b_j$，所以$b_k>b_j$。

又因为$k<j$，所以$b_k\leqslant b_j$，矛盾。

同理可证$b_k<b_j$一样不可能。

所以，如果$b_i=b_j$，那么一定有$b_i=b_{i+1}=b_{i+2}=\cdots=b_{j-1}=b_j$。

也就是说，如果$a_i=a_j$，那么区间$[b_i,b_j]$中的每一个数都只有一种可能的情况。

换言之，它们都随着$b_i$的改变而改变，所以它们只有一种可能的情况。

进一步，如果有两个重叠的区间，那么这两个区间中的每一个数应该都是相等的。

即如果$a_i=a_j,a_n=a_m$，且$i<n<j<m$（保证是重叠的），那么必有$b_i=b_{i+1}=\cdots=b_{m-1}=b_{m}$。

则此时我们就可以把区间$[b_i,b_j]$与区间$[b_n,b_m]$看作一个区间$[b_i,b_m]$。

比如样例，$a_1=a_3,a_2=a_4$，则$b_1=b_2=b_3=b_4$。

再回过头来看题，我们可以发现，我们只需要统计出那些可以$+1$的位置的数量$t$，则 $2^t$ 就是最终答案，因为可以$+1$就意味着这个位置有两种可能的情况。

$2.$实现思路

大致思路就是先输入，然后从后往前扫一遍记录下每个数最后出现的位置$r$，然后再从前往后扫一遍，途中不断更新$r$即可。

至于快速幂取余，可以去看P1226 【模板】快速幂||取余运算

至于代码，就不贴了。在明白了以上知识之后，写出一篇AC代码是很容易的啦～ （逃

$\text{The end.}$