题解归档 - cf2222C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2222C
• 本地来源：problems/cf2222C/idea.md
• 题目链接：https://codeforces.com/contest/2222/problem/C
• 原始标题：cf2222C - Median Partition

思路

cf2222C - Median Partition

Pattern

For a fixed common median value x, the partition DP is straightforward:

dp[x][i] = maximum number of valid odd-length parts covering prefix a[1..i].

For every odd subarray (l+1..r), compute its median x; then:

dp[x][r] = max(dp[x][r], dp[x][l] + 1).

This is exact because every segment in the final partition has odd length and
contributes one transition under its own median.

Algorithm

Compress array values. For every left boundary l, extend r to the right,
maintaining a Fenwick tree of the current subarray values. Whenever the length
is odd, select the middle order statistic as the median and apply the DP
transition for that median.

The table has at most n * (n+1) states, and all odd subarrays are processed
once.

Complexity

O(n^2 log n) per test case, with the official guarantee
sum n^2 <= 5000^2.

Checks

• python tools/math_reasoning_search.py --problem cf2222C -n 5 - required
  precheck done.
• python tools/run_exe.py cf2222C - sample OK.
• python tools/stress2.py cf2222C -n 500 --keep-fail - OK against slow
  median-DP brute.

代码

来源：problems/cf2222C/solution.cpp

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

struct Fenwick {
    int n = 0;
    vector<int> bit;

    Fenwick(int n_ = 0) { reset(n_); }

    void reset(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;
        for (; step; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n), vals;
        vals.reserve(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            vals.push_back(a[i]);
        }

        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        int d = (int)vals.size();
        vector<int> comp(n);
        for (int i = 0; i < n; i++) {
            comp[i] = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) + 1;
        }

        const int width = n + 1;
        vector<int> dp(d * width, -1);
        for (int v = 0; v < d; v++) dp[v * width] = 0;

        Fenwick fw(d);
        for (int l = 0; l < n; l++) {
            fw.reset(d);
            for (int r = l + 1; r <= n; r++) {
                fw.add(comp[r - 1], 1);
                int len = r - l;
                if ((len & 1) == 0) continue;
                int med = fw.kth(len / 2 + 1) - 1;
                int prev = dp[med * width + l];
                if (prev >= 0) {
                    int &to = dp[med * width + r];
                    to = max(to, prev + 1);
                }
            }
        }

        int ans = 1;
        for (int v = 0; v < d; v++) ans = max(ans, dp[v * width + n]);
        cout << ans << '\n';
    }
    return 0;
}