题面

给一个长度10^5的非负序列，序列中的0可以任意换成任何数字（包括负数），问最长严格上升子序列长度。 其中$n\le100000$

首先有个思路：决策和数与数之间$0$的个数有关系，可关系是什么呢？ 会发现对于这样的一个序列： \(a_1~~0~~...~~0~~a_2~~0~~...~~a_3\) 选择$a_2$后是否选择$a_1$与$a_1,a_2$的差值以及$a_1,a_2$间$0$的个数有关，选择$a_3$后是否选择$a_2$与$a_1-a_2,a_1-a_3$间$0$的个数又有关系…… 看了题解后发现问题可以这么转化：每一个数减去它前面出现的$0$的数量，答案即为$maxlen+cnt_0$ 以上sao操作的实质是：

我们对于每个非零数先消除前面所有零的贡献。 最后把前导零都加回去就是答案了。 -by ldx

个人理解：对于一个$0$，它可以产生1的贡献，同时将它后面所有的非$0$数全部减$1$，so……