三元上升子序列

树状数组求法

在做这道前,你需要了解树状数组求逆序对。

首先看这一道题,三元!在二元时,不是跟逆序对一样吗? 求逆序对可以用树状数组或归并,那么在三元时,是否也可以呢? 考虑 ,把它拆成两个二元 ,两个二元组都与有关,那么就考虑中间j,假设第一个不等式有 p 个 a 满足$ < a_ja >a_j$,那么以下标为j的答案就为p*q。那不就是算一下每个下标前面比它小的值,后面比它大的值。


:D 一言句子获取中...