分治 算法与 递归合并

// 版本一：递归版，最贴合「分治三步」的描述
long long qpow(long long a, long long b, long long p) {
    if (b == 0) return 1 % p;          // 递归边界：a^0 = 1（p=1 时取 0）
    long long t = qpow(a, b >> 1, p);      // 分解 + 解决：只递归一次
    t = t * t % p;                        // 合并：平方回来
    if (b & 1) t = t * a % p;             // b 是奇数，再乘一个 a
    return t;
}

// 版本二：迭代版（二进制分解），竞赛中最常用
long long qpow2(long long a, long long b, long long p) {
    long long res = 1 % p;
    a %= p;
    while (b) {
        if (b & 1) res = res * a % p;      // 这一位是 1，乘进去
        a = a * a % p;                      // 底数不断平方：a → a^2 → a^4 → a^8 ...
        b >>= 1;                            // 看下一位
    }
    return res;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, a[MAXN], tmp[MAXN];
long long ans = 0;   // 逆序对最多 n(n-1)/2，n=5e5 时约 1.25e11，必须 long long

void mergeSort(int l, int r) {
    if (l >= r) return;                 // 递归边界：只有一个元素，天然有序
    int mid = l + ((r - l) >> 1);          // 防溢出的中点写法
    mergeSort(l, mid);                     // ① 左半
    mergeSort(mid + 1, r);                 // ② 右半
    int i = l, j = mid + 1, k = l;          // ③ 合并
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) {
            tmp[k++] = a[i++];             // 左边小（或相等），正常取走
        } else {
            tmp[k++] = a[j++];             // 右边小：说明 a[i..mid] 全都 > a[j]
            ans += mid - i + 1;            // ★ 全部一次性计入
        }
    }
    while (i <= mid) tmp[k++] = a[i++];     // 左半剩余
    while (j <= r)   tmp[k++] = a[j++];     // 右半剩余
    for (int t = l; t <= r; t++) a[t] = tmp[t]; // 写回原数组
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    mergeSort(1, n);
    cout << ans << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int board[1 << 8][1 << 8];   // k ≤ 7 时 128×128 足够
int tile = 0;                      // 骨牌编号，每放一张 +1

// (tr,tc) 子棋盘左上角；(dr,dc) 该子棋盘中的残缺格；size 边长
void cover(int tr, int tc, int dr, int dc, int size) {
    if (size == 1) return;              // 边界：只剩一格，无需覆盖
    int t = ++tile;                     // 本层要用的骨牌编号
    int s = size >> 1;                   // 半边长

    // ---- 左上块 ----
    if (dr < tr + s && dc < tc + s) {     // 残缺格就在左上块
        cover(tr, tc, dr, dc, s);
    } else {                            // 否则把左上块的右下角格标为残缺
        board[tr + s - 1][tc + s - 1] = t;
        cover(tr, tc, tr + s - 1, tc + s - 1, s);
    }

    // ---- 右上块 ----
    if (dr < tr + s && dc >= tc + s) {
        cover(tr, tc + s, dr, dc, s);
    } else {
        board[tr + s - 1][tc + s] = t;      // 右上块的左下角格
        cover(tr, tc + s, tr + s - 1, tc + s, s);
    }

    // ---- 左下块 ----
    if (dr >= tr + s && dc < tc + s) {
        cover(tr + s, tc, dr, dc, s);
    } else {
        board[tr + s][tc + s - 1] = t;      // 左下块的右上角格
        cover(tr + s, tc, tr + s, tc + s - 1, s);
    }

    // ---- 右下块 ----
    if (dr >= tr + s && dc >= tc + s) {
        cover(tr + s, tc + s, dr, dc, s);
    } else {
        board[tr + s][tc + s] = t;          // 右下块的左上角格
        cover(tr + s, tc + s, tr + s, tc + s, s);
    }
}

int main() {
    int k, dr, dc; cin >> k >> dr >> dc;
    int n = 1 << k;
    board[dr][dc] = 0;                 // 0 表示不可覆盖的残缺格
    cover(1, 1, dr, dc, n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << board[i][j] << " \n"[j == n];
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const long long NEG = 0-((1LL << 62));
int n, a[MAXN];

// 分治版：返回区间 [l,r] 的最大子段和
long long solve(int l, int r) {
    if (l == r) return a[l];            // 边界：只有一个元素
    int mid = l + ((r - l) >> 1);
    long long L = solve(l, mid);          // 情况①：完全在左半
    long long R = solve(mid + 1, r);      // 情况②：完全在右半
    // 情况③：跨中线的子段 —— mid 向左的最大后缀 + mid+1 向右的最大前缀
    long long s1 = NEG, sum = 0;
    for (int i = mid; i >= l; i--) { sum += a[i]; s1 = max(s1, sum); }
    long long s2 = NEG; sum = 0;
    for (int i = mid + 1; i <= r; i++) { sum += a[i]; s2 = max(s2, sum); }
    return max(max(L, R), s1 + s2);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << "\n";

    // ---- DP 版对照（O(n)，考场推荐）----
    long long f = NEG, best = NEG;
    for (int i = 1; i <= n; i++) {
        f = max(f, 0LL) + a[i];           // 前面的和若为负，不如重新开始
        best = max(best, f);
    }
    cout << best << "\n";
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct P { double x, y; } p[MAXN], t[MAXN];
int n;

bool cmpx(const P &A, const P &B) { return A.x < B.x; }
bool cmpy(const P &A, const P &B) { return A.y < B.y; }
inline double dis(const P &A, const P &B) {
    double dx = A.x - B.x, dy = A.y - B.y;
    return sqrt(dx * dx + dy * dy);
}

// 返回 [l,r] 内的最近距离，同时把 [l,r] 按 y 归并成有序，供上一层用
double solve(int l, int r) {
    if (l == r) return 1e18;             // 只有一个点，不存在点对
    if (l + 1 == r) {                    // 只有两个点，直接算
        double d = dis(p[l], p[r]);
        if (p[l].y > p[r].y) swap(p[l], p[r]);
        return d;
    }
    int mid = l + ((r - l) >> 1);
    double mx = p[mid].x;                 // 先记下中位线，归并后 p[mid] 会变
    double d = min(solve(l, mid), solve(mid + 1, r));

    // ---- 合并：按 y 归并（分治内部维护有序，避免每层重新排序）----
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) t[k++] = (p[i].y <= p[j].y) ? p[i++] : p[j++];
    while (i <= mid) t[k++] = p[i++];
    while (j <= r)   t[k++] = p[j++];
    for (int q = l; q <= r; q++) p[q] = t[q];

    // ---- 带状区域剪枝：只取 |x - mx| < d 的点（此时 p[l..r] 已按 y 有序）----
    int m = 0;
    for (int q = l; q <= r; q++) if (fabs(p[q].x - mx) < d) t[m++] = p[q];
    for (int a = 0; a < m; a++)
        for (int b = a + 1; b < m && t[b].y - t[a].y < d; b++)   // y 差超过 d 立刻停
            d = min(d, dis(t[a], t[b]));
    return d;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p, p + n, cmpx);                 // 只有初始需要按 x 排序
    printf("%.4f\n", solve(0, n - 1));
    return 0;
}

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

// ---------- 通用分治模板：把 [l, r] 上的问题递归求解 ----------
ReturnType solve(int l, int r) {
    // ① 递归边界：规模小到可以直接算出答案
    if (l == r) return 直接答案;

    // ② 分解：取中点（或按值域 / 坐标分），保证两边规模尽量相等
    int mid = l + ((r - l) >> 1);

    // ③ 解决：递归处理两个（或多个）子问题
    ReturnType A = solve(l, mid);
    ReturnType B = solve(mid + 1, r);

    // ④ 合并：处理「跨中点」的额外情况，再与 A、B 取最优
    ReturnType C = 跨中线的答案;      // 通常是 O(规模) 的一次扫描
    return 综合(A, B, C);
}

// ---------- 使用前必做的三件事 ----------
// 1) 写出递归式，估算是否会超时（T(n)=2T(n/2)+O(n) → O(n log n)）
// 2) 检查递归边界是否覆盖「size = 1」和「size = 2」两种情况
// 3) 检查中间量是否溢出（逆序对用 long long，乘法用 __int128）