题解 | #中位数切分 | 最长上升子序列#

将大于等于 $mm$ 的数都映射为 $11$，否则映射为 $-1-1$，再求一个前缀和 $ss$

若要求分段的中位数都大于等于 $mm$，则必须 $s[n]\ge 1s[n]\; \ge \; 1$，即大于等于 $mm$ 的数的数量需要比小于 $mm$ 的数量多（很好理解，对于一个小于 $mm$ 的数，至少需要有两个大于等于 $mm$ 的数来抵消它）

而此时，要求最大分段数量，就可以转化为求最长上升子序列的问题了

若要求每一段都是合法的，那么必然需要构成最长上升子序列

对于样例：

n = 8, m = 2
x: 3  1  3  3  3  1  3  3  1
a: 1 -1  1  1  1 -1  1  1 -1
s: 1  0  1  2  3  2  3  4  3

一种最优的分段方法为：

3 || 1 3 3 || 3 1 3 3

将其转化为 $11$ 与 $-1-1$ 之后，对此我们只需要维护一个单调上升序列 $ff$ 即可，初始化为$\{0\}\backslash \{0\backslash \}$

$1.1.$ $s[1]=1>f[0]=0s[1]\; =\; 1\; >\; f[0]\; =\; 0$，将其加入到 $ff$ 中，此时 $f=\{0,1\}f\; =\; \backslash \{0,\; 1\backslash \}$

$2.2.$ $s[2]\le 0s[2]\; \backslash leq\; 0$，不可能从这里划分，不必管他

$3.3.$ $s[3]=1s[3]\; =\; 1$，$ff$ 中没有比它大的，不管

$4.4.$ $s[4]=2>f[1]=1s[4]\; =\; 2\; >\; f[1]\; =\; 1$，将其加入到 $ff$ 中，此时 $f=\{0,1,2\}f\; =\; \backslash \{0,\; 1,\; 2\backslash \}$

$5.5.$ $s[5]=3>f[2]=2s[5]\; =\; 3\; >\; f[2]\; =\; 2$，将其加入到 $ff$ 中，此时 $f=\{0,1,2,3\}f\; =\; \backslash \{0,\; 1,\; 2,\; 3\backslash \}$

$6.6.$ ，已经存在，不管

$7.7.$ $s[7]=3s[7]\; =\; 3$，$ff$ 中没有比它大的，不管

$8.8.$ $s[8]=4>f[3]=3s[8]\; =\; 4\; >\; f[3]\; =\; 3$，将其加入到 $ff$ 中，此时 $f=\{0,1,2,3,4\}f\; =\; \backslash \{0,\; 1,\; 2,\; 3,4\backslash \}$

$9.9.$ $s[9]=3s[9]\; =\; 3$，由于是最后一个元素是必选的（后续没有元素再进行抵消），所以可以通过该元素对应位置判断出应该分几段，为了使序列保持单调，找到在 $ff$ 中第一个大于 $33$ 的位置，取第一个位置到该位置的元素个数即为分段个数。

最优就是分段后每一段的和为 $11$

看$jlsjls$代码补题真不错

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n + 1);
    for(int i = 1, x; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] + (x >= m ? 1 : -1);
    }
    if(s[n] <= 0) {
        cout << -1 << "\n";
        return ;
    }
    vector<int> f{0};
    for(int i = 1; i <= n; i++) {
        if(s[i] <= 0) {
            continue;
        }
        auto it = lower_bound(f.begin(), f.end(), s[i]);
        if(i == n) {
            cout << it - f.begin() << "\n";
            return ;
        }
        if(it == f.end()) {
            f.push_back(s[i]);
        }
    }
    return ;
}