如何移除长度为K的子数组以最小化数组中的逆序数（求O(nlogn)或O(n)时间复杂度最优解法）

Great question! Let's break down how to solve this efficiently, ditching that O(n²) brute-force approach for something that runs in O(nlogn) time.

First, let's clarify what we're trying to maximize: when we remove a length-K subarray arr[i..i+K-1], the number of inversions we eliminate is the sum of three distinct groups:

1. Inversions where one element is outside the subarray (left of it) and the other is inside.
2. Inversions where one element is inside the subarray and the other is outside (right of it).
3. Inversions where both elements are inside the subarray.

The key insight here is we don't need to calculate these three groups separately. We can derive the total eliminated inversions using precomputed values, which lets us avoid redundant work.

Step 1: Precompute Contribution Arrays #

We'll start by calculating two arrays that capture each element's contribution to the total inversions:

• pre[y]: Number of elements to the left of y (0..y-1) that are larger than arr[y] (this is how much arr[y] contributes to inversions with left elements).
• suf[x]: Number of elements to the right of x (x+1..n-1) that are smaller than arr[x] (this is how much arr[x] contributes to inversions with right elements).

To compute these efficiently, we use a Fenwick Tree (Binary Indexed Tree) with value discretization (since array values might be large, we map them to a smaller range first):

Calculating pre and prefix sums #

def compute_pre(arr, sorted_unique):
    n = len(arr)
    m = len(sorted_unique)
    # Map value to its rank (1-based for Fenwick Tree compatibility)
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    fenwick = FenwickTree(m)
    pre = [0]*n
    for y in range(n):
        val_rank = rank[arr[y]]
        # Elements > arr[y] in 0..y-1 = total elements so far - elements <= arr[y]
        pre[y] = y - fenwick.query(val_rank)
        fenwick.update(val_rank, 1)
    # Prefix sum array: sum_pre[i] = sum(pre[0..i-1])
    sum_pre = [0]*(n+1)
    for i in range(n):
        sum_pre[i+1] = sum_pre[i] + pre[i]
    return pre, sum_pre

Calculating suf and prefix sums #

def compute_suf(arr, sorted_unique):
    n = len(arr)
    m = len(sorted_unique)
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    fenwick = FenwickTree(m)
    suf = [0]*n
    for x in range(n-1, -1, -1):
        val_rank = rank[arr[x]]
        # Elements < arr[x] in x+1..n-1 = elements <= arr[x]-1
        suf[x] = fenwick.query(val_rank - 1)
        fenwick.update(val_rank, 1)
    # Prefix sum array: sum_suf[i] = sum(suf[0..i-1])
    sum_suf = [0]*(n+1)
    for i in range(n):
        sum_suf[i+1] = sum_suf[i] + suf[i]
    return suf, sum_suf

Step 2: Compute Internal Inversions for All Sliding Windows #

Next, we need the number of inversions inside each length-K window. We use a sliding window approach combined with a Fenwick Tree to maintain the current window's elements efficiently:

def compute_window_inversions(arr, sorted_unique, K):
    n = len(arr)
    if K == 0:
        return [0]*n
    m = len(sorted_unique)
    rank = {v: i+1 for i, v in enumerate(sorted_unique)}
    fenwick = FenwickTree(m)
    third = [0]*(n - K + 1)
    
    # Initialize first window (0..K-1)
    total = 0
    for j in range(K-1, -1, -1):
        val_rank = rank[arr[j]]
        # Elements to the left in window that are > arr[j] = j - elements <= arr[j]
        total += j - fenwick.query(val_rank)
        fenwick.update(val_rank, 1)
    third[0] = total
    
    # Slide the window across the array
    for i in range(1, n - K + 1):
        # Remove the leftmost element of the previous window
        val_remove = arr[i-1]
        rank_remove = rank[val_remove]
        # Subtract inversions where this element was the left partner
        cnt_small = fenwick.query(rank_remove - 1)
        current = third[i-1] - cnt_small
        fenwick.update(rank_remove, -1)
        
        # Add the new right element to the window
        val_add = arr[i+K-1]
        rank_add = rank[val_add]
        # Add inversions where this element is the right partner
        cnt_large = (K-1) - fenwick.query(rank_add)
        current += cnt_large
        fenwick.update(rank_add, 1)
        
        third[i] = current
    return third

Step 3: Calculate Maximum Reduction #

For each window i..i+K-1, the total number of inversions eliminated is:

total_reduction = sum_pre_window + sum_suf_window - window_inversions

Where:

• sum_pre_window = sum of pre[y] for y in the window (sum of left contributions)
• sum_suf_window = sum of suf[x] for x in the window (sum of right contributions)
• window_inversions = internal inversions of the window (subtracted because it's counted twice in the sum of pre and suf)

We compute this for all windows and track the maximum:

def find_best_window(arr, K):
    n = len(arr)
    if K >= n:
        return 0  # Removing entire array eliminates all inversions
    # Discretize array values to handle large ranges
    sorted_unique = sorted(list(set(arr)))
    pre, sum_pre = compute_pre(arr, sorted_unique)
    suf, sum_suf = compute_suf(arr, sorted_unique)
    third = compute_window_inversions(arr, sorted_unique, K)
    
    max_reduction = -1
    best_window = 0
    for i in range(n - K + 1):
        r = i + K - 1
        sum_p = sum_pre[r+1] - sum_pre[i]
        sum_s = sum_suf[r+1] - sum_suf[i]
        reduction = sum_p + sum_s - third[i]
        if reduction > max_reduction:
            max_reduction = reduction
            best_window = i
    return best_window, max_reduction

Fenwick Tree Implementation #

Here's a simple Fenwick Tree class to support the above functions:

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0]*(self.n + 1)
    
    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx
    
    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

Key Notes #

• Discretization: Critical to handle large array values without increasing Fenwick Tree size unnecessarily.
• Efficiency: Every step runs in O(nlogn) time, so the overall complexity is O(nlogn), which meets your requirement.
• Edge Cases: Handles K = n (removes entire array, eliminates all inversions) and small K values gracefully.

内容的提问来源于stack exchange，提问作者Tyron Sequeria