2026-04-19：固定长度子数组中的最小逆序对数目。用go语言，给你一个整数数组 nums（长度为 n）和一个整数 k。所谓“逆序对”，指的是在

package main

import (
    "fmt"
    "math"
    "slices"
    "sort"
)

type fenwick []int

func (t fenwick) update(i, val int) {
    for ; i < len(t); i += i & -i {
        t[i] += val
    }
}

func (t fenwick) pre(i int) (res int) {
    for ; i > 0; i &= i - 1 {
        res += t[i]
    }
    return
}

func minInversionCount(nums []int, k int)int64 {
    // 离散化
    sorted := slices.Clone(nums)
    slices.Sort(sorted)
    sorted = slices.Compact(sorted)
    for i, x := range nums {
        nums[i] = sort.SearchInts(sorted, x) + 1// 树状数组下标从 1 开始
    }

    t := make(fenwick, len(sorted)+1)
    inv := 0
    ans := math.MaxInt

    for i, in := range nums {
        // 1. 入
        t.update(in, 1)
        inv += min(i+1, k) - t.pre(in) // 窗口大小 - (<=x 的元素个数) = (>x 的元素个数)

        left := i + 1 - k
        if left < 0 { // 尚未形成第一个窗口
            continue
        }

        // 2. 更新答案
        ans = min(ans, inv)
        if ans == 0 { // 已经最小了，无需再计算
            break
        }

        // 3. 出
        out := nums[left]
        inv -= t.pre(out - 1) // < out 的元素个数
        t.update(out, -1)
    }
    returnint64(ans)
}

func main() {
    nums := []int{5, 3, 2, 1}
    k := 4
    result := minInversionCount(nums, k)
    fmt.Println(result)
}

# -*-coding:utf-8-*-

from typing import List

class Fenwick:
    def __init__(self, n: int):
        self.n = n
        self.bit = [0] * (n + 1)
    
    def update(self, i: int, val: int) -> None:
        """将位置i增加val（i从1开始）"""
        while i <= self.n:
            self.bit[i] += val
            i += i & -i
    
    def pre(self, i: int) -> int:
        """前缀和：1到i的和"""
        res = 0
        while i > 0:
            res += self.bit[i]
            i &= i - 1
        return res

def min_inversion_count(nums: List[int], k: int) -> int:
    """
    计算所有长度为k的子数组中逆序对的最小值
    """
    # 离散化
    sorted_nums = sorted(set(nums))
    # 映射到1,2,3,...（树状数组下标从1开始）
    num_to_idx = {val: idx + 1for idx, val in enumerate(sorted_nums)}
    nums = [num_to_idx[x] for x in nums]
    
    # 树状数组
    bit = Fenwick(len(sorted_nums))
    
    inv = 0  # 当前窗口的逆序对数
    ans = float('inf')
    
    for i, num in enumerate(nums):
        # 1. 入：将当前元素加入窗口
        bit.update(num, 1)
        # 窗口大小 = min(i+1, k)
        window_size = min(i + 1, k)
        # 大于num的元素个数 = 窗口大小 - 小于等于num的元素个数
        inv += window_size - bit.pre(num)
        
        left = i + 1 - k
        if left < 0:
            # 尚未形成第一个窗口
            continue
        
        # 2. 更新答案
        ans = min(ans, inv)
        if ans == 0:
            # 已经是最小值，无需继续计算
            break
        
        # 3. 出：移除窗口最左边的元素
        out_num = nums[left]
        # 小于out_num的元素个数（这些元素与out_num构成逆序对）
        inv -= bit.pre(out_num - 1)
        bit.update(out_num, -1)
    
    returnint(ans)

def main():
    nums = [5, 3, 2, 1]
    k = 4
    result = min_inversion_count(nums, k)
    print(result)

if __name__ == "__main__":
    main()

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Fenwick {
private:
    vector<int> bit;
public:
    Fenwick(int n) : bit(n + 1, 0) {}

    void update(int i, int val) {
        for (; i < bit.size(); i += i & -i) {
            bit[i] += val;
        }
    }

    int pre(int i) {
        int res = 0;
        for (; i > 0; i &= i - 1) {
            res += bit[i];
        }
        return res;
    }
};

long long minInversionCount(vector<int>& nums, int k) {
    // 离散化
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

    for (int i = 0; i < nums.size(); i++) {
        nums[i] = lower_bound(sorted.begin(), sorted.end(), nums[i]) - sorted.begin() + 1; // 树状数组下标从1开始
    }

    Fenwick bit(sorted.size());
    int inv = 0;
    int ans = INT_MAX;

    for (int i = 0; i < nums.size(); i++) {
        int in = nums[i];

        // 1. 入
        bit.update(in, 1);
        inv += min(i + 1, k) - bit.pre(in); // 窗口大小 - (<=x的元素个数) = (>x的元素个数)

        int left = i + 1 - k;
        if (left < 0) { // 尚未形成第一个窗口
            continue;
        }

        // 2. 更新答案
        ans = min(ans, inv);
        if (ans == 0) { // 已经最小了，无需再计算
            break;
        }

        // 3. 出
        int out = nums[left];
        inv -= bit.pre(out - 1); // < out的元素个数
        bit.update(out, -1);
    }

    return (long long)ans;
}

int main() {
    vector<int> nums = {5, 3, 2, 1};
    int k = 4;
    long long result = minInversionCount(nums, k);
    cout << result << endl;
    return0;
}