算法基础：分治法核心思想与经典例题解析

分治全称为分而治之，指把一个大问题转化为几个小的子问题，当所有子问题解决后，整个大问题也就迎刃而解。下面通过四个经典案例，带你深入理解分治策略在算法竞赛中的应用。

1. 逆序对统计

以洛谷 P1908 为例，求数组中的逆序对数量是分治最经典的应用之一。

思路分析 我们将原数组从中间位置一分为二。答案由三部分组成：左半部分的逆序对、右半部分的逆序对、以及跨越左右两部分的逆序对。递归处理左右两部分直到无法划分（只剩一个元素）。合并时，由于左右两边已分别有序，可以利用双指针高效计算跨越的逆序对数。若左指针指向的值大于右指针指向的值，则左指针及其后的所有元素均构成逆序对。

代码实现

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

vector<int> v;
long long merge(int left, int right) {
    if (left >= right) return 0;
    int mid = (left + right) / 2;
    long long ret = 0;
    ret += merge(left, mid);
    ret += merge(mid + 1, right);
    
    // 归并前排序，方便统计跨越逆序对
    sort(v.begin() + left, v.begin() + mid + 1);
    sort(v.begin() + mid + 1, v.begin() + right + 1);
    
    int cur1 = left;
    int cur2 = mid + 1;
    while (cur1 <= mid && cur2 <= right) {
        if (v[cur1] <= v[cur2]) {
            cur1++;
        } else {
            ret += mid - cur1 + 1;
            cur2++;
        }
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        v.push_back(num);
    }
    cout << merge(0, v.size() - 1);
    return 0;
}

2. 求第 k 小的数

参考洛谷 P1923，利用快速排序的分区思想解决。

思路分析 定义区间 [left, right]，选取基准值 key。通过三路划分将数组分为小于 key、等于 key、大于 key 三个区间。根据 k 所在的区间范围决定下一步递归方向：若 k 落在左侧，则在左边找；若落在中间，直接返回 key；若落在右侧，则在右边找第 k-c1-c2 小的数。

代码实现

#include <iostream>
#include <vector>
using namespace std;

vector<long long> v;
long long find_kth(int left, int right, int k) {
    int begin = left;
    int cur = begin + 1;
    int end = right;
    long long key = v[left];
    
    while (cur <= end) {
        if (v[cur] > key) {
            swap(v[cur], v[end]);
            end--;
        } else if (v[cur] < key) {
            swap(v[cur], v[begin]);
            begin++;
            cur++;
        } else {
            cur++;
        }
    }
    
    int c1 = begin - left;
    int c2 = end - begin + 1;
    
    if (k <= c1) return find_kth(left, begin - 1, k);
    else if (k <= c1 + c2) return key;
    else return find_kth(end + 1, right, k - c1 - c2);
}

int main() {
    int n, k;
    cin >> n >> k;
    k++; // 调整为 1-based 索引逻辑
    v.resize(n);
    for (int i = 0; i < n; i++) scanf("%lld", &v[i]);
    cout << find_kth(0, n - 1, k) << endl;
    return 0;
}

3. 最大子段和

对应洛谷 P1115，经典的 Divide and Conquer 应用。

思路分析 将序列 [l, r] 从中间 mid 切开，最大子段和必然出现在三种情况中：完全在左半边、完全在右半边、或者跨越中轴线。前两种情况递归求解，跨越中轴线的情况需要分别求出以 mid 为起点向左延伸的最大和，以及以 mid+1 为起点向右延伸的最大和，两者相加即为跨越最大值。

代码实现

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n;
int a[N];

int dfs(int l, int r) {
    if (l == r) return a[l];
    int mid = (l + r) >> 1;
    int ret = max(dfs(l, mid), dfs(mid + 1, r));
    
    int suml = a[mid], sumr = a[mid + 1];
    int maxl = suml, maxr = sumr;
    
    for (int i = mid - 1; i >= l; i--) {
        suml += a[i];
        maxl = max(maxl, suml);
    }
    for (int i = mid + 2; i <= r; i++) {
        sumr += a[i];
        maxr = max(maxr, sumr);
    }
    return max(maxr + maxl, ret);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << dfs(1, n) << endl;
    return 0;
}

4. 地毯填补问题

对应洛谷 P1228，二维空间的分治策略。

思路分析 一维分治是将区间从中间切开，二维分治则将矩阵从中心切两刀，分成四个相等的小矩阵。假设公主在其中一个格子内，为了统一处理，我们在其余三个矩阵的中心交界处放置'假公主'（即铺设一块特殊地毯），使得四个子问题都包含一个目标点，从而可以递归继续分治。直到矩阵大小为 1x1 时停止。

代码实现

#include <iostream>
#include <vector>
using namespace std;

void dfs(int a, int b, int len, int x, int y) {
    if (len == 1) return;
    len /= 2;
    
    if (x < a + len && y < b + len) {
        cout << a + len << " " << b + len << " " << "1" << endl;
        dfs(a, b, len, x, y);
        dfs(a, b + len, len, a + len - 1, b + len);
        dfs(a + len, b, len, a + len, b + len - 1);
        dfs(a + len, b + len, len, a + len, b + len);
    } else if (x < a + len && y >= b + len) {
        cout << a + len << " " << b + len - 1 << " " << "2" << endl;
        dfs(a, b, len, a + len - 1, b + len - 1);
        dfs(a, b + len, len, x, y);
        dfs(a + len, b, len, a + len, b + len - 1);
        dfs(a + len, b + len, len, a + len, b + len);
    } else if (x >= a + len && y < b + len) {
        cout << a + len - 1 << " " << b + len << " " << "3" << endl;
        dfs(a, b, len, a + len - 1, b + len - 1);
        dfs(a, b + len, len, a + len - 1, b + len);
        dfs(a + len, b, len, x, y);
        dfs(a + len, b + len, len, a + len, b + len);
    } else {
        cout << a + len - 1 << " " << b + len - 1 << " " << "4" << endl;
        dfs(a, b, len, a + len - 1, b + len - 1);
        dfs(a, b + len, len, a + len - 1, b + len);
        dfs(a + len, b, len, a + len, b + len - 1);
        dfs(a + len, b + len, len, x, y);
    }
}

int main() {
    int k, x, y;
    cin >> k >> x >> y;
    int len = (1 << k);
    dfs(1, 1, len, x, y);
    return 0;
}