题面描述 你有 $n$ 块记忆碎片，排成一行，第 $i$ 块碎片的时间标签为 $t_i$，$(t_1, t_2, \dots, t_n)$ 是 $1$ 到 $n$ 的一个排列。 你希望通过交换把它们重排为 $[1,2,\dots,n]$。每次操作：

• 任选两块标签差值 $\le k$ 的碎片交换；
• 若两标签差值恰为 $1$，消耗 $1$ 点精力；
• 若两标签差值在 $[2,k]$ 之间，免费（消耗 $0$ 点精力）。

求：完成排序所需的最少精力。

思路

1. 如果 $k\ge3$，任何两标签间都能借助“差值$\ge2$”的免费交换连通，全程不耗能量，答案直接为 $0$。

2. 否则分两种情况：

   • $k=1$：只能做差值为 $1$ 的交换，每次都要耗能量，等价于对整个排列做相邻交换统计逆序对总数

     $$\sum_{1\le i<j\le n} [\,t_i>t_j\,]$$

   • $k=2$：差值为 $2$ 的交换免费，可在“同奇偶”标签之间任意重排；只有“奇↔偶”标签的逆序需要消耗能量。最少精力即所有逆序对中“奇偶性不同”的数目

   

3. 统计手段：

   • $k=1$ 时，用归并排序法 $O(n\log n)$ 统计全逆序对。
   • $k=2$ 时，维护两棵树状数组（BIT）：一棵存右侧剩余的奇数标签计数，一棵存偶数计数；扫描时对每个元素查询并累加与其不同奇偶的、比它小的右侧标签数量。

C++

#include <bits/stdc++.h>
using namespace std;

// 归并法统计全部逆序对（k=1）
long long count_all_inv(vector<int>& a) {
    int n = a.size();
    vector<int> tmp(n);
    function<long long(int,int)> dfs = [&](int l, int r) {
        if (r-l <= 1) return 0LL;
        int m = (l + r) >> 1;
        long long cnt = dfs(l, m) + dfs(m, r);
        int i = l, j = m, p = l;
        while (i < m || j < r) {
            if (j==r || (i<m && a[i]<=a[j])) tmp[p++] = a[i++];
            else {
                cnt += (m - i);
                tmp[p++] = a[j++];
            }
        }
        for (int k = l; k < r; k++) a[k] = tmp[k];
        return cnt;
    };
    return dfs(0, n);
}

// 树状数组（Fenwick Tree）
struct BIT {
    int n;
    vector<int> t;
    BIT(int _n): n(_n), t(n+1,0) {}
    void update(int i, int v=1) {
        for (; i<=n; i+=i&-i) t[i]+=v;
    }
    int query(int i) {
        int s=0;
        for (; i>0; i-=i&-i) s+=t[i];
        return s;
    }
    int query(int l, int r) {
        return query(r) - query(l-1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> t(n);
    for (int i = 0; i < n; i++) cin >> t[i];

    if (k >= 3) {
        // 全程免费
        cout << 0 << "\n";
        return 0;
    }
    if (k == 1) {
        // 只允许相邻交换，耗能 = 全逆序对数
        cout << count_all_inv(t) << "\n";
        return 0;
    }
    // k == 2：免费交换同奇偶，只计算奇偶不同的逆序对
    BIT bit_even(n), bit_odd(n);
    // 初始化：把所有标签放入对应 BIT
    for (int x : t) {
        if (x & 1) bit_odd.update(x);
        else       bit_even.update(x);
    }
    long long ans = 0;
    // 从左向右，把当前标签从“右侧集合”中移出，并查询与之不同奇偶且小于它的剩余标签数
    for (int x : t) {
        if (x & 1) {
            bit_odd.update(x, -1);
            ans += bit_even.query(x-1);
        } else {
            bit_even.update(x, -1);
            ans += bit_odd.query(x-1);
        }
    }
    cout << ans << "\n";
    return 0;
}

Python

import sys
sys.setrecursionlimit(10**7)

# 归并法统计全部逆序对（k=1）
def merge_all(a, tmp, l, r):
    if r-l <= 1: return 0
    m = (l+r)//2
    cnt = merge_all(a, tmp, l, m) + merge_all(a, tmp, m, r)
    i, j, p = l, m, l
    while i < m or j < r:
        if j==r or (i<m and a[i]<=a[j]):
            tmp[p] = a[i]; i += 1
        else:
            cnt += (m - i)
            tmp[p] = a[j]; j += 1
        p += 1
    a[l:r] = tmp[l:r]
    return cnt

# 树状数组
class BIT:
    def __init__(self,n):
        self.n = n
        self.t = [0]*(n+1)
    def update(self,i,v=1):
        while i<=self.n:
            self.t[i] += v
            i += i&-i
    def query(self,i):
        s = 0
        while i>0:
            s += self.t[i]
            i -= i&-i
        return s
    def range_query(self,l,r):
        return self.query(r) - self.query(l-1)

def main():
    data = list(map(int, sys.stdin.read().split()))
    n, k = data[0], data[1]
    t = data[2:]

    if k >= 3:
        print(0)
        return

    if k == 1:
        tmp = [0]*n
        print(merge_all(t, tmp, 0, n))
    else:
        # k == 2
        bit_even = BIT(n)
        bit_odd  = BIT(n)
        for x in t:
            if x & 1: bit_odd.update(x)
            else:     bit_even.update(x)

        ans = 0
        for x in t:
            if x & 1:
                bit_odd.update(x, -1)
                ans += bit_even.query(x-1)
            else:
                bit_even.update(x, -1)
                ans += bit_odd.query(x-1)
        print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    // 归并统计全部逆序对（k=1）
    static long mergeAll(int[] a, int l, int r, int[] tmp) {
        if (r - l <= 1) return 0;
        int m = (l + r) >> 1;
        long cnt = mergeAll(a, l, m, tmp) + mergeAll(a, m, r, tmp);
        int i = l, j = m, p = l;
        while (i < m || j < r) {
            if (j==r || (i<m && a[i] <= a[j])) tmp[p++] = a[i++];
            else {
                cnt += (m - i);
                tmp[p++] = a[j++];
            }
        }
        System.arraycopy(tmp, l, a, l, r-l);
        return cnt;
    }

    // 树状数组
    static class BIT {
        int n;
        int[] t;
        BIT(int n) { this.n = n; t = new int[n+1]; }
        void update(int i, int v) {
            while (i <= n) { t[i] += v; i += i & -i; }
        }
        int query(int i) {
            int s = 0;
            while (i > 0) { s += t[i]; i -= i & -i; }
            return s;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
        int[] t = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) t[i] = Integer.parseInt(st.nextToken());

        if (k >= 3) {
            System.out.println(0);
            return;
        }

        if (k == 1) {
            System.out.println(mergeAll(t, 0, n, new int[n]));
        } else {
            // k == 2
            BIT bitEven = new BIT(n), bitOdd = new BIT(n);
            for (int x : t) {
                if ((x & 1) == 1) bitOdd.update(x, 1);
                else                bitEven.update(x, 1);
            }
            long ans = 0;
            for (int x : t) {
                if ((x & 1) == 1) {
                    bitOdd.update(x, -1);
                    ans += bitEven.query(x-1);
                } else {
                    bitEven.update(x, -1);
                    ans += bitOdd.query(x-1);
                }
            }
            System.out.println(ans);
        }
    }
}

题目内容

你得到了$n$块[记忆碎片]，它们排成一排，第$i$块碎片所对应记忆发生的时间为$t_i。t_1,t_2,...,t_n$是$1$到$n$的一个排列。

你希望重新排列这$n$块碎片，使它们单调递增(即重排为$1,2,...,n$)，排列的规则为:

• 你有一个能力值$k$，每次你可以选择两块发生时间相差不超过$k$的碎片，交换它们的顺序;

• 由于发生时间过于靠近的两块碎片很难回想，对于两块发生时间相差恰好为1的碎片，交换它们需要消耗你$1$点精力;

• 对于发生时间相差大于$1$的碎片，变换它们则不需要耗费精力。

  你想知道你最少需要消耗多少精力才能恢复你的[记忆]。

输入描述

第一行输入两个整数$n,k(4≦n≦2×10^5;1≦k≦n-1)$代表[记忆碎片]的个数、你的能力值。

第二行输入$n$个不同的整数$t_1,t_2,...,t_n(1≦t_i≦n)$,其中,$t_i$代表第$i$块[记忆碎片]所对应记忆的发生时间。

输出描述

输出一个整数，表示你最少需要消耗的精力。

样例1

输入

4 1
2 1 3 4

输出

1

说明

在这个样例中，交换$t_1$和$t_2$即可，我们可以证明，最少需要消耗$1$点精力

样例2

输入

4 3
2 1 3 4

输出

0

说明

最优交换策略为:

• 交换$t_2$ 和$t_4$，得到{$2,4,3,1$};

• 交换$t_1$和$t_2$,得到{$4,2,3,1$};

• 交换$t_1$和$t_4$,得到{$1,2,3,4$}。

  至此，$t$已经有序，最少需要消耗$0$点精力。