Tóm tắt đề bài

Cho dãy \(a_1, a_2, \ldots, a_n\). Ta muốn cắt dãy thành nhiều đoạn liên tiếp nhất có thể, rồi mỗi đoạn được sắp xếp riêng (không giảm), cuối cùng ghép các đoạn theo thứ tự ban đầu sao cho toàn bộ dãy thu được là không giảm. Hãy tính số đoạn lớn nhất có thể cắt.

Phân tích

• Nếu ta cắt tại vị trí \(i\) (tức là kết thúc một đoạn ở \(i\)), thì sau khi sắp xếp các đoạn, phần tử trong đoạn trước phải “khớp” đúng với những phần tử tương ứng trong mảng đã sắp xếp toàn cục.
• Gọi \(b\) là mảng \(a\) sau khi sắp xếp không giảm.

• Một quan sát then chốt:

  Ta có thể kết thúc một đoạn tại vị trí \(i\) khi và chỉ khi đa tập các phần tử trong tiền tố \(a[1..i]\) giống hệt đa tập các phần tử trong tiền tố \(b[1..i]\).

Vì khi đó, sau khi sắp xếp đoạn đầu tiên (và các đoạn trước đó), các phần tử ở vị trí \(1..i\) trong kết quả cuối cùng có thể đúng bằng \(b[1..i]\), nên ta “chốt” được biên đoạn tại \(i\) mà không phá vỡ thứ tự toàn cục.

• Do \(a_i\) có thể trùng nhau, không thể chỉ so sánh “max tiền tố” như bài toán với hoán vị; phải so sánh theo tần suất (đa tập).

Hướng giải quyết

Nhận xét

Ta duyệt từ trái sang phải, duy trì chênh lệch tần suất giữa tiền tố của \(a\) và tiền tố của \(b\):

• Khi đọc \(a[i]\): tăng đếm của giá trị đó.
• Khi đọc \(b[i]\): giảm đếm của giá trị đó.
• Nếu mọi chênh lệch đều về \(0\) (tức cấu trúc đếm rỗng), thì hai tiền tố là cùng đa tập \(\Rightarrow\) có thể cắt tại \(i\).

Thuật toán (đúng như code AC)

1. Đọc \(n\), mảng \(a\).
2. Tạo \(b = a\), rồi sort(b).
3. Khởi tạo map<ll,int> mp lưu chênh lệch tần suất.
4. Với mỗi \(i\) từ \(0\) đến \(n-1\):
5. mp[a[i]]++
6. mp[b[i]]--
7. Xóa các khóa có giá trị \(0\) để kiểm tra rỗng nhanh:
   - Trong code: lặp xóa ở mp.begin() khi phần tử đầu có giá trị \(0\).
8. Nếu mp rỗng: tăng đáp án (kết thúc được một đoạn tại đây).
9. In đáp án.

Trực giác vì sao tối ưu (cắt được nhiều nhất)

• Ta “tham” cắt ngay tại mọi vị trí hợp lệ (khi đa tập tiền tố khớp).
• Việc cắt sớm nhất có thể không làm mất đi khả năng cắt về sau, vì điều kiện hợp lệ chỉ phụ thuộc vào tiền tố. Mỗi lần mp rỗng là một mốc chắc chắn có thể hoàn tất đúng \(b[1..i]\), nên cắt tại đó luôn an toàn và giúp tăng số đoạn.

Lưu ý/Pitfall

• Có phần tử trùng nhau nên phải dùng tần suất, không dùng chỉ số hay max.
• Cần dùng kiểu long long cho giá trị \(a_i\).
• Xóa khóa có đếm \(0\) để kiểm tra rỗng chính xác (và tránh map phình to). Code AC chỉ xóa ở begin(), vẫn đúng vì mục tiêu chỉ là biết mp có rỗng hay không; nếu còn khóa khác bằng \(0\) không ở begin() thì mp vẫn không rỗng và ta chưa đếm đoạn tại đó (nhưng liệu có thể xảy ra khi tất cả đều \(0\)?). Khi tất cả đều \(0\) thì phần tử nhỏ nhất cũng \(0\) nên vòng while sẽ xóa hết dần và mp rỗng.

Độ phức tạp

• Sắp xếp: \(O(n \log n)\).
• Duyệt và cập nhật map: mỗi bước \(O(\log n)\), tổng \(O(n \log n)\).
• Bộ nhớ: \(O(n)\) (mảng và map tần suất).

Code tham khảo

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

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

    int n;
    cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    b = a;
    sort(b.begin(), b.end());

    // mp[x] = (số lần x xuất hiện trong a[0..i]) - (số lần x xuất hiện trong b[0..i])
    map<ll, int> mp;
    int ans = 0;

    for (int i = 0; i < n; i++) {
        mp[a[i]]++;
        mp[b[i]]--;

        // Xóa các khóa có giá trị 0 (bắt đầu từ khóa nhỏ nhất).
        while (!mp.empty() && mp.begin()->second == 0) {
            mp.erase(mp.begin());
        }

        // Nếu mp rỗng => hai tiền tố có cùng đa tập => cắt được tại i
        if (mp.empty()) ans++;
    }

    cout << ans;
    return 0;
}