严谨证明其实真的很难
设每次操作为\((l,r,x)\)，其中\(l,r\)表示操作的左右端点，\(x\)表示乘以的值
首先我们知道，最后由于严格升序，所以数列分成三段，第一段为负数，第二段为\(0\)，第三段为正数；操作之间的顺序无关紧要；操作之间不会跨段：如果有跨段，那么一定是跨了三段（只跨两段的话，有一段就是\(0\)，就相当于没有跨段）；如果某个跨段的操作的\(x\)为负数，设为\((l,r,x)\)，那么所有满足左端点为\(l\)右端点为\(r\)的段的个数一定是偶数，所以可以将所有\(x\)取反，也就是说此时所有跨段的操作的\(x\)都是正数，而这种段的作用只有可能让\(＜\)变成\(≥\)，为负作用，还不如不要，于是可以去掉；所以不存在跨段的操作
实际上不会有乘以\(0\)的操作（也就是数列不会出现\(0\)）。假设有\((l,r,0)\)，由于最后严格升序，所以\(l=r\)；而对任意一种包含\((l,l,0)\)的方案，我们都可以去掉\((l,l,0)\)，并将正数段的所有操作的\(x\)变成一个很大的值（但是不改变正数段的严格升序性）来使得序列仍然满足条件
于是现在分别考虑两段的操作。
对于正数段，可以将所有操作的\(r\)变成\(n\)而不改变严格升序性，这样的话一次操作最多只能让一个\(≥\)变成\(＜\)，所以\(≥\)的个数就是答案
对于负数段，我们先考虑所有形如\((1,r,x)\)的操作。这些操作显然有奇数个（因为\(a_1\)是负数）。设这些操作的\(r\)的最大值为\(r_{\text{max}}\)，那么任取一个\((1,r_{\text{max}},x)\)，并将其他所有的\((1,r,x)\)的\(x\)取绝对值，显然不会改变序列的样子；此时再对\([2,r_{\text{max}}]\)考虑同样的事情，将每一个\(a_i\)被负数覆盖的次数变成刚好为一次，即就是\((1,r_{\text{max}},x)\)；然后从\(r_{\text{max}}+1\)开始重复，最后会发现所有的负数段互相不重叠，且之间没缝隙；此时我们将所有正数段的\(l\)全部变成\(1\)（这样显然不改变严格升序性），然后全部放在负数段里面，具体来说，被整个正数段完整跨过的负数段的\(x\)乘以这个正数段的\(x\)，没有完整跨过的的负数段拆成两段，前一段的\(x\)乘以这个正数段的\(x\)，后一个的\(x\)不变，如下
这样操作次数显然不变且序列不变；最终负数段就会变成互不重叠且之间没有空隙的段；而一个负数段会将其内部的符号全部取反，所以一个负数段的内部的符号一定没有\(≤\)，所以\(≤\)的个数就是下界
标签：Sorting,text,跨段,升序,负数,Multiplication,操作,正数 From： https://www.cnblogs.com/dingxingdi/p/18359279