Editorial for Ranh giới của bình minh

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 — xét vị trí kết thúc của đoạn cuối

Gọi dp[i] là số cách chia hợp lệ đoạn đầu gồm i phần tử. Nếu đoạn cuối là [j+1, i], ta cần kiểm tra khi nào giá trị lớn nhất nằm ở đầu trái hoặc đầu phải.

Gợi ý 2 — dùng hai mốc gần nhất lớn hơn

Gọi p[i] là vị trí gần nhất đứng trước i có a[p[i]] > a[i]. Đoạn cuối có giá trị lớn nhất ở đầu phải khi và chỉ khi j >= p[i]; phần này được tính bằng tổng đoạn của các dp[j].

Các trường hợp đầu trái là lớn nhất được gom bằng một mốc phụ. Gọi g[i] là vị trí gần nhất trước i có a[g[i]] >= a[i]. Khi đó:

  • extra[i] = extra[g[i]] + dp[i-1].
  • dp[i] = sum(dp[j], j = p[i]..i-1) + extra[p[i]].

Dùng hai ngăn xếp đơn điệu để tìm p[i], g[i]; dùng mảng cộng dồn để tính tổng trong O(1). Dấu so sánh khác nhau là cần thiết: mốc thứ nhất bỏ các giá trị bằng nhau, mốc thứ hai giữ lại chúng.

Lời giải đầy đủ

Ý tưởng

Mỗi cách chia hợp lệ có đúng một đoạn cuối. Xét điểm cắt ngay trước đoạn đó.

Đặt dp[0] = 1. Với mỗi i, nếu p[i] là phần tử gần nhất trước i có giá trị lớn hơn a[i], thì các điểm cắt j >= p[i] tạo đoạn cuối mà a[i] là giá trị lớn nhất ở đầu phải.

Các đoạn có giá trị lớn nhất ở đầu trái được gom trong extra[p[i]]. Một ứng viên đầu trái phải nằm trên chuỗi mốc "gần nhất trước đó có giá trị lớn hơn hoặc bằng". Vì vậy, nếu g[i] là mốc này thì extra[i] = extra[g[i]] + dp[i-1].

Hai nhóm được cộng không đếm trùng: p[i] dùng điều kiện lớn hơn nghiêm ngặt, còn chuỗi g gom các đầu trái trước mốc lớn hơn a[i]. Mọi phép tính lấy modulo 10^9+7.

Độ phức tạp

Mỗi phần tử được đưa vào và lấy ra khỏi mỗi ngăn xếp nhiều nhất một lần. Thời gian O(N), bộ nhớ O(N).

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

const int MOD = 1'000'000'007;

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    vector<int> prevGreater(n + 1), prevGreaterEqual(n + 1);
    vector<int> st;

    // Mốc gần nhất có giá trị lớn hơn a[i].
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
        prevGreater[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }

    st.clear();
    // Mốc gần nhất có giá trị lớn hơn hoặc bằng a[i].
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && a[st.back()] < a[i]) st.pop_back();
        prevGreaterEqual[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }

    vector<int> dp(n + 1), pref(n + 1), extra(n + 1);
    dp[0] = 1;
    pref[0] = 1;  // pref[i] = dp[0] + ... + dp[i]

    auto rangeSum = [&](int l, int r) {
        if (l > r) return 0;
        int result = pref[r] - (l == 0 ? 0 : pref[l - 1]);
        if (result < 0) result += MOD;
        return result;
    };

    for (int i = 1; i <= n; ++i) {
        int p = prevGreater[i];
        dp[i] = (rangeSum(p, i - 1) + extra[p]) % MOD;
        pref[i] = (pref[i - 1] + dp[i]) % MOD;
        extra[i] = (extra[prevGreaterEqual[i]] + dp[i - 1]) % MOD;
    }

    cout << dp[n] << '\n';
    return 0;
}

Loading...