Bảy Núi (Đề tự luyện HSG Tin 12 – Bài 2)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhĐếm đoạn conHai con trỏĐoạn đơn điệulong long

Đề bài

Bảy Núi. Có $N$ cột mốc liên tiếp, cột thứ $i$ cao $h_i$ mét. Đoạn $[l, r]$ ($l \le r$) gọi là hình ngọn núi nếu có $p$ ($l \le p \le r$) sao cho $h_l \le h_{l+1} \le \ldots \le h_p$ và $h_p \ge h_{p+1} \ge \ldots \ge h_r$. Đoạn một cột mốc, đoạn chỉ đi lên hay chỉ đi xuống cũng là hình ngọn núi. Hãy đếm số đoạn hình ngọn núi.

Dữ liệu vào: dòng đầu $N$ ($1 \le N \le 3 \cdot 10^5$); dòng hai $h_1, \ldots, h_N$ ($1 \le h_i \le 10^9$).

Kết quả: số đoạn $[l, r]$ là hình ngọn núi.

• Subtask 1 (20%): $N \le 300$.
• Subtask 2 (30%): $N \le 5000$.
• Subtask 3 (50%): không có ràng buộc gì thêm.

Input

10
3 1 4 1 5 9 2 6 5 3

Output

26

Giải thích

$10$ đoạn một cột, $9$ đoạn hai cột đều là hình ngọn núi. Các đoạn dài hơn là hình ngọn núi: $[2, 4]$, $[4, 6]$, $[4, 7]$, $[5, 7]$, $[7, 9]$, $[7, 10]$, $[8, 10]$. Tổng $10 + 9 + 7 = 26$.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Bảy Núi

Lời mở đầu

Bài đếm đoạn con quen thuộc: có $\frac{N(N+1)}{2}$ đoạn, với $N = 3 \cdot 10^5$ là khoảng $4{,}5 \cdot 10^{10}$ đoạn – không thể kiểm tra từng đoạn. Ta cần một nhận xét để đếm "theo lô".

Nhận xét 1 (tính "di truyền"). Nếu $[l, r]$ là hình ngọn núi thì cắt bớt một cột ở đầu trái, đoạn $[l + 1, r]$ vẫn là hình ngọn núi (nếu đỉnh $p = l$ thì đoạn còn lại chỉ đi xuống, vẫn hợp lệ). Vì vậy, với mỗi đầu phải $r$, các đầu trái hợp lệ tạo thành một khoảng liền $[L(r), r]$ và

$$\text{đáp án} = \sum_{r=1}^{N} \big(r - L(r) + 1\big).$$

Nhận xét 2 (tìm $L(r)$). Đứng ở $r$ nhìn sang trái: đi ngược lại, trước hết là đoạn sườn xuống (đọc từ trái sang phải là không tăng), sau đó là đoạn sườn lên (không giảm). Muốn đi xa nhất, ta đi hết sườn xuống tới đỉnh $p$ xa nhất, rồi đi hết sườn lên từ $p$.

Hình 1. Với $r = 7$: lùi qua sườn xuống $9 \ge 2$ tới $p = 6$, rồi lùi qua sườn lên $1 \le 5 \le 9$ tới $l = 4$. Có $4$ đoạn hình ngọn núi kết thúc tại cột $7$.

Cách 1Kiểm tra từng đoạn · 20%Cách 2Cố định l, kéo dài r · 50%Cách 3Mảng sườn lên/xuống · 100%

Cách 1Kiểm tra từng đoạn – O(N³) · 20%

Duyệt mọi cặp $(l, r)$. Để kiểm tra đoạn $[l, r]$, cho con trỏ $p$ chạy từ $l$: leo lên chừng nào còn $h_p \le h_{p+1}$, rồi đi xuống chừng nào còn $h_p \ge h_{p+1}$. Đoạn là hình ngọn núi khi và chỉ khi $p$ đi tới được $r$.

Vì sao leo "tham lam" hết cỡ là đúng?

Nếu có một đỉnh $p^*$ hợp lệ thì $p$ leo được ít nhất tới $p^*$. Nếu $p$ leo vượt quá $p^*$ thì các bước đó vừa không giảm (vì leo được) vừa không tăng (vì nằm trên sườn xuống của $p^*$) – tức là đi ngang, nên từ chỗ dừng vẫn đi xuống được tới $r$.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<long long> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    long long ans = 0;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            int p = l;
            while (p < r && h[p] <= h[p + 1]) p++;   // leo len (khong giam) xa nhat co the
            while (p < r && h[p] >= h[p + 1]) p++;   // roi di xuong (khong tang)
            if (p == r) ans++;                       // di tron toi r: hinh ngon nui
        }
    cout << ans << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    h = [0] + [int(x) for x in data[1:1 + n]]
    ans = 0
    for l in range(1, n + 1):
        for r in range(l, n + 1):
            p = l
            while p < r and h[p] <= h[p + 1]:   # leo len (khong giam) xa nhat co the
                p += 1
            while p < r and h[p] >= h[p + 1]:   # roi di xuong (khong tang)
                p += 1
            if p == r:                          # di tron toi r: hinh ngon nui
                ans += 1
    print(ans)


main()

Không gian$O(N)$

Thời gian$O(N^3)$

Cách 2Cố định l, kéo dài r – O(N²) · 50%

Thay vì kiểm tra lại từ đầu, cố định $l$ rồi tăng dần $r$, nhớ một cờ down = "đã bắt đầu đi xuống chưa". Khi thêm cột $r$:

• nếu $h_r < h_{r-1}$: đang đi xuống, bật down = true;
• nếu $h_r > h_{r-1}$ mà down đã bật: đi xuống rồi lại lên – đoạn hỏng, và mọi $r$ lớn hơn cũng hỏng (Nhận xét 1 theo chiều ngược lại), nên break;
• nếu $h_r = h_{r-1}$: đi ngang, không ảnh hưởng gì.

Mỗi $r$ chưa bị break là một đoạn hợp lệ.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    long long ans = 0;
    for (int l = 1; l <= n; l++) {
        bool down = false;                     // da bat dau di xuong chua?
        ans++;                                 // doan [l, l]
        for (int r = l + 1; r <= n; r++) {
            if (h[r] < h[r - 1]) down = true;  // bat dau (hoac van) di xuong
            else if (h[r] > h[r - 1] && down) break;  // dang xuong ma lai len: hong
            ans++;                             // [l, r] van la hinh ngon nui
        }
    }
    cout << ans << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    h = [0] + [int(x) for x in data[1:1 + n]]
    ans = 0
    for l in range(1, n + 1):
        down = False                  # da bat dau di xuong chua?
        ans += 1                      # doan [l, l]
        for r in range(l + 1, n + 1):
            if h[r] < h[r - 1]:
                down = True           # bat dau (hoac van) di xuong
            elif h[r] > h[r - 1] and down:
                break                 # dang xuong ma lai len: hong
            ans += 1                  # [l, r] van la hinh ngon nui
    print(ans)


main()

Không gian$O(N)$

Thời gian$O(N^2)$ trong trường hợp xấu nhất

Dữ liệu ngẫu nhiên thì Cách 2 chạy rất nhanh?

Đúng vậy, vì các ngọn núi ngẫu nhiên rất ngắn nên break sớm. Nhưng nếu có một ngọn núi dài $2 \cdot 10^5$ cột (hoặc tất cả các cột cao bằng nhau!) thì vòng lặp trong chạy hết cỡ – khoảng $2 \cdot 10^{10}$ bước. Bộ test subtask 3 test nào cũng có một ngọn núi rất dài.

Cách 3Mảng sườn lên/xuống – O(N) · 100%

Theo hai nhận xét ở Lời mở đầu, ta chỉ cần tính nhanh $L(r)$. Định nghĩa:

• down[i] = vị trí bắt đầu của đoạn không tăng dài nhất kết thúc tại $i$ (sườn xuống);
• up[i] = vị trí bắt đầu của đoạn không giảm dài nhất kết thúc tại $i$ (sườn lên).

Cả hai tính trong một lượt: down[i] = down[i-1] nếu $h_{i-1} \ge h_i$, ngược lại down[i] = i; up tương tự với $h_{i-1} \le h_i$. Khi đó đỉnh xa nhất là p = down[r] và $L(r)$ = up[p]; cộng r - up[p] + 1 vào đáp án.

Vì sao $L(r)$ = up[down[r]] là nhỏ nhất? Với mọi đỉnh $p'$ hợp lệ của đoạn kết thúc tại $r$ thì $p' \ge$ down[r] = $p$. Nếu $p' > p$: các cột từ $p$ tới $p'$ nằm trên sườn xuống của $r$; sườn lên tới $p'$ muốn vượt qua $p$ về bên trái thì đoạn $[p, p']$ phải vừa không tăng vừa không giảm, tức là bằng phẳng – khi đó nó đi tiếp đúng như sườn lên của $p$. Vậy không đỉnh nào cho $l$ nhỏ hơn up[p].

Đây cũng chính là "hai con trỏ": khi $r$ tăng thì $L(r)$ không giảm (Nhận xét 1), nhưng nhờ hai mảng ta nhảy thẳng tới $L(r)$ chứ không cần dịch từng bước.

Cẩn thận với các cột cao bằng nhau

Đi ngang ($h_{i-1} = h_i$) thuộc cả sườn lên lẫn sườn xuống, nên up dùng <= và down dùng >=. Dùng so sánh chặt ở một trong hai chỗ là sai; ví dụ dãy $1, 3, 2, 2, 1$: cả đoạn là hình ngọn núi nhưng nếu sườn xuống dùng > thì chỉ lùi được tới cột $4$.

Đếm theo đỉnh thì sao?

Một cách nghe rất hợp lý: với mỗi đỉnh $p$, số đoạn nhận $p$ làm đỉnh = (số cách chọn $l$) × (số cách chọn $r$), rồi cộng lại. Cách này đúng khi không có hai cột kề nhau cao bằng nhau (ví dụ của đề là như vậy!), nhưng với đoạn bằng phẳng thì một đoạn có nhiều đỉnh và bị đếm nhiều lần – ví dụ $N$ cột cao bằng nhau ra tới $\frac{N(N+1)(N+2)}{6}$ thay vì $\frac{N(N+1)}{2}$.

Tràn số

Đáp án tới $\frac{N(N+1)}{2} \approx 4{,}5 \cdot 10^{10}$: biến đếm phải là long long.

Các bạn nhập dãy độ cao (tối đa 12 cột) và bấm "Tiếp" để xem từng $r$:

Độ cao h

Ví dụ nhanh:

Code hoàn chỉnh:

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    vector<int> up(n + 1), down(n + 1);
    // up[i]: vi tri bat dau cua doan KHONG GIAM dai nhat ket thuc tai i
    // down[i]: vi tri bat dau cua doan KHONG TANG dai nhat ket thuc tai i
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        up[i] = (i > 1 && h[i - 1] <= h[i]) ? up[i - 1] : i;
        down[i] = (i > 1 && h[i - 1] >= h[i]) ? down[i - 1] : i;
        int p = down[i];          // dinh xa nhat ve ben trai: [p, i] khong tang
        int l = up[p];            // [l, p] khong giam
        ans += i - l + 1;         // moi doan [l..i, i] deu hinh ngon nui
    }
    cout << ans << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    h = [0] * (n + 1)
    for i in range(1, n + 1):
        h[i] = int(data[i])
    up = [0] * (n + 1)      # up[i]: dau doan khong giam dai nhat ket thuc tai i
    down = [0] * (n + 1)    # down[i]: dau doan khong tang dai nhat ket thuc tai i
    ans = 0
    for i in range(1, n + 1):
        if i > 1 and h[i - 1] <= h[i]:
            up[i] = up[i - 1]
        else:
            up[i] = i
        if i > 1 and h[i - 1] >= h[i]:
            down[i] = down[i - 1]
        else:
            down[i] = i
        ans += i - up[down[i]] + 1   # dinh p = down[i], dau trai l = up[p]
    sys.stdout.write(str(ans) + "\n")


main()

Không gian$O(N)$

Thời gian$O(N)$

C++▶ Chạy tay từng dòng codeTheo dõi mảng up, down, đỉnh p, đầu trái l và đáp án.

Dữ liệu vào (stdin) – sửa thoải mái10 3 1 4 1 5 9 2 6 5 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false); cin.tie(nullptr);

5 int n;

6 cin >> n;

7 vector<long long> h(n + 1);

8 for (int i = 1; i <= n; i++) cin >> h[i];

9 vector<int> up(n + 1), down(n + 1);

10 // up[i]: vi tri bat dau cua doan KHONG GIAM dai nhat ket thuc tai i

11 // down[i]: vi tri bat dau cua doan KHONG TANG dai nhat ket thuc tai i

12 long long ans = 0;

13 for (int i = 1; i <= n; i++) {

14 up[i] = (i > 1 && h[i - 1] <= h[i]) ? up[i - 1] : i;

15 down[i] = (i > 1 && h[i - 1] >= h[i]) ? down[i - 1] : i;

16 int p = down[i]; // dinh xa nhat ve ben trai: [p, i] khong tang

17 int l = up[p]; // [l, p] khong giam

18 ans += i - l + 1; // moi doan [l..i, i] deu hinh ngon nui

19 }

20 cout << ans << "\n";

21 return 0;

22}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 30 test: 10 test subtask 1 ($N \le 300$), 9 test subtask 2 ($N = 5000$), 11 test subtask 3 ($N = 3 \cdot 10^5$). Ở subtask 2 và 3, test nào cũng có một ngọn núi rất dài (ít nhất $4000$ cột ở subtask 2, ít nhất $1{,}5 \cdot 10^5$ cột ở subtask 3) để các cách chậm không thể "ăn may"; nhiều test có sườn lên, sườn xuống, đỉnh và thung lũng bằng phẳng; có test tất cả các cột cao bằng nhau.

Cách làm	Sub 1 (20%)	Sub 2 (30%)	Sub 3 (50%)	Điểm
Cách 1 – kiểm tra từng đoạn	Đúng	TLE	TLE	20
Cách 2 – cố định l, kéo dài r	Đúng	Đúng	TLE	50
Cách 3 – mảng sườn lên/xuống	Đúng	Đúng	Đúng	100
Sai 1 – biến đếm kiểu int	Đúng	Đúng	WA	50
Sai 2 – so sánh chặt cả hai sườn (<, >)	4/10 test	1/9 test	WA	≈ 11
Sai 3 – sườn xuống so sánh chặt (>)	5/10 test	2/9 test	1/11 test	≈ 21
Sai 4 – đếm theo đỉnh: Σ (số cách chọn l) × (số cách chọn r)	4/10 test	1/9 test	WA	≈ 11

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và chạy quá 3 giây ở mọi test sau; Cách 2 đúng hết hai subtask đầu, chạy quá 3 giây ở cả 11 test subtask 3; Cách 3 đúng 30/30 test, test lâu nhất khoảng 0,02 giây. Ba lời giải sai về "cao bằng nhau" đều ra đúng ví dụ của đề (vì ví dụ không có hai cột kề nhau cao bằng nhau) nhưng mất gần hết điểm – đọc kỹ dấu $\le$, $\ge$ trong định nghĩa là "nút thắt" của bài này.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇