type
status
date
slug
summary
tags
category
icon
password
在做这道前,你需要了解树状数组求逆序对
首先看这一道题,三元!在二元时,不是跟逆序对一样吗?
求逆序对可以用树状数组或归并,那么在三元时,是否也可以呢?
考虑 ,把它拆成两个二元 ,,两个二元组都与 有关,那么就考虑中间 ,假设第一个不等式有 个 满足 ,第二个有 个 满足 ,那么以下标为 的答案就为 。就是算一下每个元素前面比它小的个数,后面比它大的个数
此题可以拓展到 元上升序列,推荐个大佬博客