判断题 适中
#24797

在一个数组中,如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ,则 a[i] 和 a[j] 是一个逆 序对。 下面代码可以正…

在一个数组中,如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ,则 a[i] 和 a[j] 是一个逆 序对。

下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

long long cnt=0;
void merge_count(vector<int>& a, int l, int m, int r){
    int i = l, j = m + 1;
    while(i <= m && j <= r) {
        if(a[i] <= a[j]) i++;
        else {
            cnt += (m - i + 1);
            j++;
        }
    }
}


未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析
1. 将区间 [l,r] 拆分为两个已排序的子区间 [l,m] 和 [m+1,r]; 2. 使用双指针 i 和 j 分别指向两个子区间的起始位置; 3. 当 a[i] <= a[j] 时,a[i] 不构成与右区当前元素及后续元素的逆序关系,i++; 4. 当 a[i] > a[j] 时,左区从 i 到 m 的所有元素均大于 a[j],累计贡献 (m - i + 1) 到计数器; 5. j++,继续处理下一个右区元素; 6. 循环直至任一子区间遍历完毕。