大概就是许多人这题复杂度写的是不对的…写法大概是线段树上只维护 p[i] 的区间最大值，询问的时候根据这个在线段树上二分。但这个二分是假的，复杂度是 $O(\sum (\zeta(i))\cdot \rm poly\log)$，其中 $\zeta(i)$ 是 $i$ 的决策点个数。那也就是说大概是如下程序的 $cnt$ 值乘上一个 $\rm polylog$：

for (int i = 1 ; i <= n + 1 ; ++ i)
    for (int j = i - 1, mx = 0 ; j >= 0 ; -- j)
        if (pos[j] >= mx && pos[j] < pos[i])
            mx = pos[j], ++ cnt ;

然后这个复杂度是显然不对的。考虑将题目中的 $\{p_n\}$ 按照这种方式生成：

n/2,n/2-1,n/2-2……1,n,n-1,n-2……n/2+1

那么就可以轻易被卡到 $n^2$ 。

链接:https://pan.baidu.com/s/1WeQD6qsORfyUmX6LeONuRw 密码:ua1f

由于不会写 Validator 所以大家可以自行测一下自己的程序

不过在不特别卡的情况下，这个 $cnt$ 会是 $O(n\ln n)$ 的级别。据 mls 说是跟单调栈在每个位置的期望长度之和是一个界。这也是为什么这些错解能过掉的原因。