题解：AT_abc396_f [ABC396F] Rotated Inversions

题目翻译

给定整数

N

，

M

和一个长度为

N

的非负整数序列

A

。对于每个

k=0,1,\dots,M-1

，计算序列

B

的逆序数。其中

B_i=(A_i+k)mod

M

。

逆序数的定义是满足

1\le i < j\le N

且

B_i>B_j

的整数对数目。

问题分析

我们需要计算每个

k

对应的逆序数。直接对每个

k

生成序列

B

并计算逆序数的时间复杂度是

O(MNlogN)

，这显然不可行。我们需要预处理和数学规律来快速计算每个

k

的结果。

关键思路

预处理贡献值：当 $k$ 变化时，某些元素会“绕圈”（即 $B_i = A_i+k-M$ ），这会影响逆序数的计算。预处理每个元素绕圈时的贡献变化。
初始逆序数：使用归并排序计算 $k=0$ 时的逆序数。
动态调整逆序数：根据 $k$ 的变化，利用预处理的值调整逆序数，避免重复计算。

步骤

计算初始逆序数：使用归并排序计算 $k=0$ 时的逆序数。
预处理贡献值： $sum[a]$ 记录当元素 $a$ 开始绕圈时，后面比它小的元素数目（减少的逆序对数）。 $sum$ _ $[a]$ 记录当元素 $a$ 开始绕圈时，前面比它大的元素数目（新增的逆序对数）。
动态调整：对于每个 $k$ ，调整初始逆序数，减去减少的贡献值，加上新增的贡献值。

代码

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,ans,a[200001],b[200001],cnt[200001],sum[200001],cnt_[200001],sum_[200001];
// 归并排序计算逆序数
void merge(int l,int r){
    if(l>=r)return;
    int mid=(l+r)/2;
    merge(l,mid);merge(mid+1,r);
    int i=l,j=mid+1,cnt=l;
    while(i<=mid && j<=r){
        if(a[i]<=a[j])b[cnt++]=a[i++];
        else{
            b[cnt++]=a[j++];
            ans+=mid-i+1; // 统计逆序对
        }
    }
    while(i<=mid)b[cnt++]=a[i++];
    while(j<=r)b[cnt++]=a[j++];
    for(int k=l;k<=r;k++)a[k]=b[k];
}
signed main(){
    cin >> n >> m;
    for(int i=1;i<=n;i++)cin >> a[i];
    // 预处理 sum 数组：从后往前统计每个元素绕圈后的贡献
    for(int i=n;i>=1;i--){
        cnt[a[i]]++; // 记录当前元素出现次数
        sum[a[i]]+=(n-i+1-cnt[a[i]]); // 后面非 a[i] 的元素数目
    }
    // 预处理 sum_ 数组：从前往后统计每个元素绕圈后的贡献
    for(int i=1;i<=n;i++){
        cnt_[a[i]]++;
        sum_[a[i]]+=(i-cnt_[a[i]]); // 前面非 a[i] 的元素数目
    }
    // 计算初始逆序数（k=0 的情况）
    merge(1,n);
    cout << ans << "\n";
    // 处理每个 k 从 1 到 M-1
    for(int k=1;k<m;k++){
        ans=ans-sum[m-k]+sum_[m-k];
        cout << ans << "\n";
    }
    return 0;
}

代码注释

归并排序：用于计算初始逆序数（ $k=0$ 时的结果）。
预处理 $sum$ 和 $sum$ _： $sum[a]$ 统计当元素 $a$ 绕圈时，后面比它小的元素数目。 $sum$ _ $[a]$ 统计当元素 $a$ 绕圈时，后面比它大的元素数目。
动态调整：对于每个 $k$ ，调整逆序数，利用预处理的值快速计算。

时间复杂度

O(N

log

N+M)

题解：AT_abc396_f [ABC396F] Rotated Inversions

文章操作

题目翻译

问题分析

关键思路

步骤

代码

代码注释

时间复杂度

相关推荐

评论

题解：AT_abc396_f [ABC396F] Rotated Inversions