1 条题解

  • 0
    @ 2024-6-11 10:53:06

    树状数组进行每个长度的的统计逆序对,然后当遇到每一个数的时候进行统计如果取反,会在原本的逆序对基础上进行的变化有哪些。

    变化为

    1.如果在一个区间上选择第i个点,那么这个数前面的i-1个点肯定都大于它。

    2.然后统计这个数后面比他还要小的数(防止重复贡献)

    例如 5 4 3 2 1 如果是3这个数变成-3,即:5 4 -3 2 1那么我们的5 4都是逆序对, 但是末尾的2 1并不是逆序对了,这里就需要进行减掉2 1 和原本3组成的逆序对。

    • 1

    信息

    ID
    811
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    70
    已通过
    10
    上传者