线性基

恕我语文不好，实在不晓得用何种词汇来描述看到下文的感受：

此比赛为正常的提高组难度，甚至可以用来作为普及组模拟赛。 请选手 AK 后不要大声喧哗，以免影响他人 AK。

尤其是这套题的出题人是张隽铠的情况下。当然，OI 圈风气本就如此，我也不好过多评价。No comment.

T1 还算顺利，半小时左右搞定。T2 是大分类讨论，足够恶心人，但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关，但没有相应知识储备，暴力跑路。

T4 就……反正出题人开心就好。到现在都没人改出来。

一句话题解

A – 序列

依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一，否则违背题意。

于是枚举子序列首元素，将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 $\operatorname{O}(n \log n)$。 （更多…）