题解：AT_abc396_f [ABC396F] Rotated Inversions

yuzipeng · 2025-03-13 21:26:57 · 题解

题目翻译

给定整数 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，调整初始逆序数，减去减少的贡献值，加上新增的贡献值。

代码

#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)