题解：最少正确分段数问题

题目分析

本题要求将序列划分为最少数量的“正确片段”，其中每个片段需满足：首项是片段的最小值，末项是片段的最大值。我们可以通过单调栈预处理最小值位置和线段树维护最大值位置的方法来高效解决这个问题。

方法思路

1. 单调栈预处理最小值影响范围：使用单调栈找出每个位置i右侧第一个比a[i]小的元素位置minv[i]。这表示以i为起点的片段，最远只能延伸到minv[i]-1（否则会出现更小的元素，破坏“首项是最小值”的条件）。
2. 线段树维护区间最大值位置：在每个可能的片段区间[i, minv[i]-1]中，找到最大值的位置maxv。该位置即为当前片段的最优分割点（满足“末项是最大值”的条件）。
3. 贪心分段：每次从i开始，找到最优分割点maxv后，下一个片段从maxv+1开始，重复此过程直到遍历完整个序列。

解决代码

#include <bits/stdc++.h>

namespace FastIO {
using namespace std;
const int S = 1 << 20;
char buf[S], *p1 = buf, *p2 = buf;
char getchar() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, S, stdin)) == buf ? EOF : *p1++;
}
void read(char &c) {
    for (c = getchar(); c != EOF && c < 33; c = getchar())
        ;
}
void read(string &s) {
    s.clear();
    char c = getchar();

    for (; c != EOF && c < 33; c = getchar());

    for (; c != EOF && c > 32; c = getchar())
        s.push_back(c);
}
void read(char *s, int st) {
    char c = getchar();

    for (; c != EOF && c < 33; c = getchar());

    for (; c != EOF && c > 32; c = getchar())
        s[st++] = c;

    s[st] = '\0';
}
template <typename type>
void read(type &res) {
    type x = 0, f = 1;
    char c = getchar();

    for (; c < 48 || c > 57; c = getchar())
        f = c == '-' ? -f : f;

    for (; c > 47 && c < 58; c = getchar())
        x = (x << 3) + (x << 1) + (c ^ 48);

    res = f * x;
}
template <typename type, typename ...Args>
void read(type &x, Args &...args) {
    read(x), read(args...);
}
template <typename type>
void print(type x) {
    char s[40], t[40];
    int p = 0, len = 0;

    if (x < 0) {
        s[len++] = '-';
        x = -x;
    }

    do {
        t[p++] = char('0' + x % 10);
        x /= 10;
    } while (x);

    while (p--)
        s[len++] = t[p];

    fwrite(s, 1, len, stdout);
}
void print(const string &s) {
    fwrite(s.data(), 1, s.size(), stdout);
}
void print(const char *s) {
    fwrite(s, 1, strlen(s), stdout);
}
void print(const char c) {
    fwrite(&c, 1, 1, stdout);
}
template<typename type, typename ...Args>
void print(type x, Args ...args) {
    print(x), print(args...);
}
void IOS() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
}
}

using namespace std;
using FastIO::read;
using FastIO::print;
using FastIO::IOS;

const int N = 300010;

int n, ans;
int a[N], minv[N];
struct SegmentTree {
#define ls p << 1
#define rs p << 1 | 1
    struct point {
        int id, dat;
        bool operator < (const point &Other) const {
            if (dat == Other.dat)
                return id < Other.id;
            return dat < Other.dat;
        }
    } t[N << 2];
    void pushup(int p) {
        t[p] = max(t[ls], t[rs]);
    }
    void build(int p, int L, int R) {
        if (L == R)
            return void(t[p] = {L, a[L]});
        int mid = (L + R) >> 1;
        build(ls, L, mid);
        build(rs, mid + 1, R);
        pushup(p);
    }
    point ask(int p, int L, int R, int l, int r) {
        if (l <= L && r >= R)
            return t[p];
        point res = {0, 0};
        int mid = (L + R) >> 1;
        if (l <= mid)
            res = max(res, ask(ls, L, mid, l, r));
        if (r > mid)
            res = max(res, ask(rs, mid + 1, R, l, r));
        return res;
    }
} T;
stack<int> s;

int main() {
    IOS();
    read(n);
    for (int i = 1; i <= n; i++)
        read(a[i]);
    
    // 单调栈求每个位置右侧第一个更小的元素位置
    for (int i = 1; i <= n; i++) {
        for (; !s.empty() && a[i] < a[s.top()]; s.pop())
            minv[s.top()] = i;
        s.push(i);
    }
    // 处理栈中剩余元素
    for (int i = 1; i <= n; i++)
        minv[i] = !minv[i] ? n + 1 : minv[i];
    
    T.build(1, 1, n);  // 线段树构建，维护区间最大值的位置
    
    // 贪心分段
    for (int i = 1; i <= n; i++) {
        int r = minv[i];
        int maxv = T.ask(1, 1, n, i, r - 1).id;
        ans++;
        i = maxv;
    }
    
    print(ans);
    return 0;
}

代码解释

• FastIO 模块：用于快速读写数据，适配大规模输入（如 ( n \leq 3 \times 10^5 )）。
• 单调栈预处理 minv 数组：minv[i] 表示位置 i 右侧第一个比 a[i] 小的元素位置，以此确定以 i 为起点的片段的右边界上限。
• 线段树 SegmentTree：维护区间内最大值的位置，用于快速查询每个可能片段的最优分割点（满足“末项是最大值”的位置）。
• 贪心分段逻辑：从左到右遍历，每次找到当前片段的最优分割点后，跳转到该点的下一个位置继续处理，确保每段都是正确片段且总段数最少。

该方法的时间复杂度为 ( O(n \log n) )，能够高效处理题目中的最大数据规模。