Problem Description

Given a permutation of length n and an integer k, partition the array in to k contiguous segments such that the sum of inversion counts within each segment is minimized.

Constraints: n ≤ 25000, k ≤ 25

Solution Approach

This problem can be solved using dynamic programming with decision monotonicity and divide-and-conquer optimization.

Dynamic Programming Formulation

Let dp[i][j] represent the minimum inversion count sum when partitioning the first i elements into j segments.

Let inv_count(l, r) denote the number of inversoins in the subarray [l, r]. The recurrence relation is:

dp[i][j] = min<sub>k=0</sub><sup>i-1</sup> { dp[k][j-1] + inv_count(k+1, i) }

Decision Monotonicity

The cost function satisfies the quadrangle inequality. For indices p1 ≤ p2 ≤ p3 ≤ p4:

inv_count(p1, p3) + inv_count(p2, p4) ≤ inv_count(p1, p4) + inv_count(p2, p3)

This property enables efficient optimization using divide-and-conquer.

Implementation Strategy

The solution uses a Fenwick Tree to count inversions and a Mo's algorithm-like pointer movement to efficiently compute inversion counts during the divide-and-conquer process.

Algorithm Complexity

Time complexity: O(nk log²n)

Code Implementation

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 25005;
const int MAXK = 30;
const int INF = 0x3f3f3f3f;

int arr[MAXN], dp[MAXN], prev_dp[MAXN];
int left_ptr, right_ptr, current_inversions;

struct FenwickTree {
    int tree[MAXN];
    
    int lowbit(int x) { return x & -x; }
    
    void update(int pos, int delta) {
        for (int i = pos; i <= n; i += lowbit(i)) 
            tree[i] += delta;
    }
    
    int query(int pos) {
        int sum = 0;
        for (int i = pos; i > 0; i -= lowbit(i))
            sum += tree[i];
        return sum;
    }
} bit;

void adjust_range(int target_left, int target_right) {
    while (left_ptr > target_left) {
        left_ptr--;
        int larger_count = (right_ptr - left_ptr + 1) - bit.query(arr[left_ptr]);
        current_inversions += larger_count;
        bit.update(arr[left_ptr], 1);
    }
    while (right_ptr < target_right) {
        right_ptr++;
        current_inversions += bit.query(arr[right_ptr] - 1);
        bit.update(arr[right_ptr], 1);
    }
    while (left_ptr < target_left) {
        int larger_count = (right_ptr - left_ptr + 1) - bit.query(arr[left_ptr]);
        current_inversions -= larger_count;
        bit.update(arr[left_ptr], -1);
        left_ptr++;
    }
    while (right_ptr > target_right) {
        current_inversions -= bit.query(arr[right_ptr] - 1);
        bit.update(arr[right_ptr], -1);
        right_ptr--;
    }
}

void divide_conquer(int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    
    int mid = (l + r) / 2;
    int best_cost = INF, best_pos = -1;
    
    for (int i = min(opt_r, mid - 1); i >= opt_l; i--) {
        adjust_range(i + 1, mid);
        int candidate = prev_dp[i] + current_inversions;
        if (candidate < best_cost) {
            best_cost = candidate;
            best_pos = i;
        }
    }
    
    dp[mid] = best_cost;
    divide_conquer(l, mid - 1, opt_l, best_pos);
    divide_conquer(mid + 1, r, best_pos, opt_r);
}

int main() {
    int n, k;
    cin >> n >> k;
    
    for (int i = 1; i <= n; i++) 
        cin >> arr[i];
    
    // Initialize base case for k=1
    memset(bit.tree, 0, sizeof(bit.tree));
    for (int i = 1; i <= n; i++) {
        prev_dp[i] = prev_dp[i-1] + bit.query(arr[i] - 1);
        bit.update(arr[i], 1);
    }
    
    if (k == 1) {
        cout << prev_dp[n] << endl;
        return 0;
    }
    
    left_ptr = 1, right_ptr = 0;
    memset(bit.tree, 0, sizeof(bit.tree));
    
    for (int segments = 2; segments <= k; segments++) {
        divide_conquer(segments, n, segments - 1, n);
        memcpy(prev_dp, dp, sizeof(dp));
    }
    
    cout << dp[n] << endl;
    return 0;
}