P1637 三元上升子序列 分析

__ryp__ · 2024-02-02 05:25:48 · 个人记录

考虑到我们可以枚举中间值，然后要求的就是在每个元素之前，小于这个元素以及大于这个元素的元素数量。用乘法原理即可得到最后答案。

形式化地，我们设 l_i 是 1 到 i - 1 中小于 x_i 的元素数量，r_i 对称，那么最终答案就是 \sum\limits_{i=1}^{n} l_i\times r_i。

那么我们就是要求参数 l_i 与 r_i。考虑离线 + 离散化 + 树状树组。这里树状树组实际上就是个桶前缀和。

然后做法明显。