P4528 题解

Piggy343288 · 2023-06-23 21:33:00 · 题解

这篇题解并不做任何形式上的理论推导，而是在于引导像我一样的蒟蒻，如何在遇到这样的题时，不会陷入数据结构暴力分别求三种形态的深渊里无法自拔。

看到这道题我们的第一想法应该是把三种形态的数量都求出来，如果可以的话，这题马上就秒掉了。那么我们尝试着去求——

• 比较简单的可能是高山形态的个数。你可能会想到把这个东西扔到主席树上做什么节点的和什么乱七八糟的东西，总之好像可以做，但在 n\log n 的时间复杂度内是很困难的。
• 遇到闪电的时候，问题一下子更复杂了起来。1324 形的东西，太难维护！考虑枚举 1 的位置 i，然后你要求的就是对于所有 i<j<k<m，满足 a[m]>a[j]>a[k]>a[i] 的个数……诶怎么一点优化也没有啊？而且这东西形状如此之具体特殊，我们想要一次性的找出一大堆贡献是不容易的。

注意我们最后一句话，“这东西形状如此之具体特殊，我们想要一次性的找出一大堆贡献是不容易的”，我们是否可以考虑通过一些其他方法，运用正难则反的思想解决问题？

此时，我们发现了另一个诡异的地方：原题并未要求求出三种形态，而是求出一个差值。理论上，如果能求出具体值的话应该求出具体值才对，毕竟我们考虑一种极端的情况，即三种形态都算错了一点恰好差值一样（可能是落下了边界条件？）；再考虑多输出两个数字并没有什么影响，我们断定这里有猫腻。

因此我们考虑推柿子，最后我们惊讶的发现 1324-1243-1432=1x2x-1xxx+13xx+1234。我们不难看出后者在处理上的优越性：并未对形态有过于具体的要求（例如 1x2x,1xxx,13xx 是很优秀的形态），或者形态很好处理（1234）。综上，一个学数据结构学傻了的孩子顺利的得出了本题的正解。

写这篇题解已经是我会做这道题以后，因此有些部分未免牵强。但我写这篇题解，主要是因为此题并不难在数据结构的维护，而是在于“这是怎么想到的”。因此我尽量还原一个人做这道题的大致思路，希望对于大家有帮助。