题解

思路推导

把最后保留的递增子序列染成白色，把被删除的递减子序列染成黑色，问题等价于能否把所有元素分成一个递增子序列和一个递减子序列。

对排列中的四个按位置递增的元素观察其相对大小。若它们形成 $3412$ 或 $2143$ 模式，则前两个元素与后两个元素分别迫使两种颜色发生矛盾，因此这样的序列一定不是好的。反过来，可以按位置依次延伸两条单调链；若第一次无法放置当前元素，沿着导致矛盾的两条链回溯，恰能抽取出上述两种四元模式之一。因此，一个排列是好的，当且仅当它同时避开 $3412$ 与 $2143$。

好性质对子数组取子数组仍然成立。固定左端点 $l$，存在一个最小右端点 $r_l$，使 $p[l\ldots r_l]$ 首次包含禁用四元模式；从 $l$ 开始的好子数组数量就是 $r_l-l$。若不存在这样的右端点，令 $r_l=n+1$。

做法

先用小规模二染色暴力和四元模式枚举确认禁用模式刻画，再在满分范围内分别寻找两类模式的最早右端点。两次扫描的结果合并后做后缀最小值，并按左端点累加合法右端点数量。

部分分做法

当 $n\le 14$ 时，可以枚举每个子数组以及所有二染色方案，直接检查白色元素是否严格递增、黑色元素是否严格递减。

当 $n\le 100$ 时，枚举全部四元组。若四元组形成 $3412$ 或 $2143$，便用它的首、尾位置更新首次失败边界；随后对首位置做后缀最小值，即可得到所有 $r_l$。

满分做法

分别处理 $3412$ 和 $2143$。对 $3412$，先用两个方向的单调栈建立“前方最近可接的小值”和“后方最近可接的大值”关系。按中间枢轴从右向左扫描，把已经激活的右端候选按数值加入树状数组；树状数组维护每个值前缀中最小的下标。这样每条左侧关系只需一次前缀最小值查询，就能得到以相应位置为首端的最早 $3412$ 右端点。

把所有值 $p_i$ 替换为 $n+1-p_i$ 后，$2143$ 与 $3412$ 互相转换，复用同一过程即可得到另一类禁用模式。对两类结果取最小值，再做一次后缀最小值，便得到每个左端点的 $r_l$。最后累加 $r_l-l$。

正确性证明

由二染色等价关系与禁用模式刻画，子数组为好当且仅当它不包含 $3412$ 或 $2143$。单调栈枚举了形成每个模式时必须跨越的两侧支配关系，树状数组查询在所有已激活右端候选中返回下标最小且数值满足条件者，因此得到的是每个可能首位置对应的最早禁用模式末位置。值取补映射把两种模式一一对应，所以两次扫描覆盖且只覆盖全部禁用模式。

后缀最小值把“模式首位置恰为 $i$”转化为“模式首位置不小于 $l$”，恰好对应子数组左端为 $l$ 时能够包含的所有模式。于是 $[l,r_l-1]$ 及其前缀都好，而从 $r_l$ 开始都不好，贡献为 $r_l-l$。累加后得到全部好子数组数。

复杂度分析

满分算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。