Cây bẹo (Đề 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ó: KháChặt nhị phân đáp ánHai con trỏDeque đơn điệuHàng đợi ưu tiên

Đề bài

Cây bẹo. $N$ ghe đậu thành hàng ở chợ nổi, cây bẹo của ghe $i$ cao $h_i$. Khung ảnh của dãy ghe liên tiếp $[l, r]$ có diện tích $S(l, r) = (r - l + 1) \cdot \max(h_l, \ldots, h_r)$. Xếp diện tích của tất cả $\frac{N(N+1)}{2}$ dãy theo thứ tự không giảm (trùng nhau vẫn tính riêng), hãy cho biết diện tích thứ $K$.

Dữ liệu vào: dòng đầu $N, K$ ($1 \le N \le 3 \cdot 10^5$, $1 \le K \le \frac{N(N+1)}{2}$); dòng hai gồm $h_1, \ldots, h_N$ ($1 \le h_i \le 10^9$).

Kết quả: diện tích thứ $K$.

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

Input

4 6
3 1 4 2

Output

8

Giải thích

10 diện tích: dãy 1 ghe 3, 1, 4, 2; dãy 2 ghe 6, 8, 8; dãy 3 ghe 12, 12; dãy 4 ghe 16. Xếp lại: 1, 2, 3, 4, 6, 8, 8, 12, 12, 16 → tấm thứ 6 có diện tích 8.

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 Cây bẹo

Lời mở đầu

Đề cho một đại lượng quen thuộc: diện tích hình chữ nhật có đáy là đoạn $[l, r]$ và chiều cao là phần tử lớn nhất trong đoạn.

Hình 1. Ví dụ đề: khung ảnh của dãy ghe 2–3 phải cao bằng cây bẹo của ghe 3.

Ba nhận xét làm nên lời giải:

• Đơn điệu theo hai đầu. Nới dãy thêm một ghe thì chiều rộng tăng, chiều cao không giảm, nên diện tích không giảm: $S(l, r) \le S(l, r+1)$ và $S(l, r) \le S(l-1, r)$.
• "Thứ K" = "nhỏ nhất mà đếm đủ K". Gọi $cnt(X)$ là số dãy có diện tích $\le X$. Hàm này không giảm theo $X$. Diện tích thứ $K$ chính là số $X$ nhỏ nhất thoả $cnt(X) \ge K$. Đây là dạng chặt nhị phân trên đáp án rất hay gặp khi đề hỏi "phần tử thứ K" của một tập quá lớn để liệt kê.
• Số rất lớn. Diện tích tới $3 \cdot 10^5 \cdot 10^9 = 3 \cdot 10^{14}$ và $K$ tới $4{,}5 \cdot 10^{10}$, nên mọi biến đều phải là long long.

Cách 1Liệt kê hết · 20%Cách 2Hàng đợi ưu tiên · 50%Cách 3Chặt nhị phân + hai con trỏ · 100%

Cách 1Liệt kê mọi dãy – O(N² ) · 20%

Cố định $l$ rồi cho $r$ chạy từ $l$ sang phải, cập nhật mx = max(mx, h[r]) là có ngay $S(l, r)$ trong $O(1)$. Ta thu được đúng $\frac{N(N+1)}{2}$ số. Với $N = 2000$ là khoảng $2 \cdot 10^6$ số – vừa bộ nhớ. Muốn lấy phần tử thứ $K$ thì dùng nth_element (trung bình $O(\text{số phần tử})$), hoặc sắp xếp cũng được.

Với $N = 3 \cdot 10^5$ có $4{,}5 \cdot 10^{10}$ dãy, không thể lưu cũng không thể duyệt hết.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    long long K;
    cin >> n >> K;
    vector<long long> h(n), s;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int l = 0; l < n; l++) {
        long long mx = 0;
        for (int r = l; r < n; r++) {
            mx = max(mx, h[r]);           // max cua h[l..r]
            s.push_back((r - l + 1) * mx);
        }
    }
    nth_element(s.begin(), s.begin() + (K - 1), s.end());
    cout << s[K - 1] << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    h = list(map(int, data[2:2 + n]))
    s = []
    for l in range(n):
        mx = 0
        for r in range(l, n):
            if h[r] > mx:
                mx = h[r]              # max cua h[l..r]
            s.append((r - l + 1) * mx)
    s.sort()
    print(s[K - 1])


main()

Không gian$O(N^2)$

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

Cách 2Trộn N dãy tăng bằng hàng đợi ưu tiên – O((N + K) log N) · 50%

Với mỗi $l$ cố định, dãy $S(l, l), S(l, l+1), S(l, l+2), \ldots$ là dãy không giảm (nhận xét 1). Vậy ta có $N$ "hàng" đã sắp sẵn, cần lấy ra $K$ số nhỏ nhất của cả $N$ hàng. Cách làm giống như trộn nhiều dãy đã sắp xếp:

• Ban đầu đưa phần tử đầu của mỗi hàng vào hàng đợi ưu tiên (min-heap): bộ $(S(l,l), l, l, h_l)$.
• Lặp $K - 1$ lần: lấy ra bộ nhỏ nhất $(S, l, r, mx)$ và đưa vào phần tử kế tiếp của hàng đó: $(r + 2 - l) \cdot \max(mx, h_{r+1})$. Ta lưu kèm $mx$ để khỏi tính lại max.
• Phần tử ở đỉnh heap sau đó chính là diện tích thứ $K$.

Heap luôn có không quá $N$ phần tử, mỗi thao tác $O(\log N)$. Khi $K \le 10^6$ thì chạy rất nhanh, và cũng đúng cho subtask 1 (khi đó $K \le 2 \cdot 10^6$). Nhưng ở subtask 3, $K$ có thể lên tới $4{,}5 \cdot 10^{10}$ thì cách này hết đường.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    long long K;
    cin >> n >> K;
    vector<long long> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    // moi phan tu: (dien tich, l, r, max h[l..r]); lay nho nhat truoc
    priority_queue<tuple<long long, int, int, long long>,
                   vector<tuple<long long, int, int, long long>>, greater<>> pq;
    for (int l = 0; l < n; l++) pq.push({h[l], l, l, h[l]});
    for (long long t = 1; t < K; t++) {
        auto [s, l, r, mx] = pq.top();
        pq.pop();
        if (r + 1 < n) {                  // noi dai day [l, r] sang phai
            long long m2 = max(mx, h[r + 1]);
            pq.push({(r + 2 - l) * m2, l, r + 1, m2});
        }
    }
    cout << get<0>(pq.top()) << "\n";
    return 0;
}

import sys
import heapq


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    h = list(map(int, data[2:2 + n]))
    # moi phan tu: (dien tich, l, r, max h[l..r]); lay nho nhat truoc
    pq = [(h[l], l, l, h[l]) for l in range(n)]
    heapq.heapify(pq)
    for _ in range(K - 1):
        s, l, r, mx = heapq.heappop(pq)
        if r + 1 < n:                     # noi dai day [l, r] sang phai
            m2 = max(mx, h[r + 1])
            heapq.heappush(pq, ((r + 2 - l) * m2, l, r + 1, m2))
    print(pq[0][0])


main()

Không gian$O(N)$

Thời gian$O((N + K) \log N)$

Cách 3Chặt nhị phân đáp án + hai con trỏ + deque – O(N log(N·H)) · 100%

Bước 1 – chặt nhị phân. Theo nhận xét 2, ta tìm $X$ nhỏ nhất có $cnt(X) \ge K$ trong đoạn $[1, N \cdot \max h]$ (dãy cả hàng ghe có diện tích đúng bằng $N \cdot \max h$, nên $cnt$ tại đó bằng $\frac{N(N+1)}{2} \ge K$). Số $X$ tìm được chắc chắn là diện tích của một dãy nào đó: nếu không thì $cnt(X - 1) = cnt(X) \ge K$, trái với tính nhỏ nhất. Chặt nhị phân mất khoảng $\log_2(3 \cdot 10^{14}) \approx 49$ lần gọi $cnt$.

Chạy tay với ví dụ đề ($K = 6$):

lo	hi	mid	cnt(mid)	So với K = 6
1	16	8	7	≥ 6 → hi = 8
1	8	4	4	< 6 → lo = 5
5	8	6	5	< 6 → lo = 7
7	8	7	5	< 6 → lo = 8
8	8	lo = hi = 8 → đáp án 8

Bước 2 – đếm $cnt(X)$ trong $O(N)$ bằng hai con trỏ. Với mỗi đầu phải $r$, các đầu trái $l$ cho diện tích $\le X$ tạo thành một đoạn $[p(r), r]$ (vì thu hẹp từ trái thì diện tích không tăng). Hơn nữa $p(r) \le p(r+1)$: nếu $S(l, r+1) \le X$ thì $S(l, r) \le X$. Do đó con trỏ trái $l$ chỉ cần tiến, không bao giờ lùi:

• Tăng $r$, rồi chừng nào $(r - l + 1) \cdot \max(h_l..h_r) > X$ thì tăng $l$.
• Cộng $r - l + 1$ vào kết quả (số dãy kết thúc tại $r$ có diện tích $\le X$; có thể bằng 0 khi $h_r > X$).

Bước 3 – lấy max của cửa sổ trượt bằng deque. Cửa sổ $[l, r]$ chỉ thêm phần tử bên phải và bỏ phần tử bên trái, nên dùng deque đơn điệu: lưu các chỉ số với $h$ giảm dần. Khi thêm $r$, bỏ khỏi cuối deque mọi chỉ số có $h \le h_r$ (chúng nằm bên trái $r$ và không cao hơn, nên không bao giờ còn là max). Khi $l$ vượt qua chỉ số ở đầu deque thì bỏ nó. Max cửa sổ luôn là $h[\text{đầu deque}]$. Mỗi chỉ số vào và ra deque nhiều nhất một lần, nên tổng cộng vẫn $O(N)$.

Bẫy "giữ một biến max"

Nhiều bạn chỉ giữ biến mx = max(mx, h[r]) và quên rằng khi $l$ tăng thì max có thể giảm. Khi đó diện tích bị tính lớn hơn thật, số đếm bị thiếu và đáp án sai. Cách sai này vẫn đúng với dãy tăng (max luôn nằm ở mép phải), nên vẫn ăn may được vài test.

Các bạn thử mô phỏng hàm đếm với dãy và $X$ tuỳ ý:

Độ cao h X

Ví dụ nhanh:

Bản C++ dùng mảng dq với hai chỉ số head, tail thay cho std::deque (nhanh hơn và giống hệt bản Python). Lưu ý (r - l + 1) * h[dq[head]] có kiểu long long vì h là mảng long long.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300005;
int n, dq[MAXN];
long long K, h[MAXN];
// dem so khung anh co dien tich <= X
long long countLE(long long X) {
    int head = 0, tail = 0, l = 0;  // dq[head..tail-1]: chi so, h giam dan
    long long cnt = 0;
    for (int r = 0; r < n; r++) {
        while (tail > head && h[dq[tail - 1]] <= h[r]) tail--;
        dq[tail++] = r;
        while (l <= r && (r - l + 1) * h[dq[head]] > X) {
            l++;
            if (dq[head] < l) head++;
        }
        cnt += r - l + 1;
    }
    return cnt;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> K;
    long long mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
        mx = max(mx, h[i]);
    }
    long long lo = 1, hi = n * mx;  // dap an nam trong [lo, hi]
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        if (countLE(mid) >= K) hi = mid;
        else lo = mid + 1;
    }
    cout << lo << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    h = list(map(int, data[2:2 + n]))
    dq = [0] * n
    lo, hi = 1, n * max(h)          # dap an nam trong [lo, hi]
    while lo < hi:
        X = (lo + hi) // 2
        # dem so khung anh co dien tich <= X (hai con tro + deque)
        cnt = 0; l = 0; head = 0; tail = 0
        for r in range(n):
            hr = h[r]
            while tail > head and h[dq[tail - 1]] <= hr:
                tail -= 1
            dq[tail] = r; tail += 1
            while l <= r and (r - l + 1) * h[dq[head]] > X:
                l += 1
                if dq[head] < l:
                    head += 1
            cnt += r - l + 1
        if cnt >= K:
            hi = X
        else:
            lo = X + 1
    print(lo)


main()

Không gian$O(N)$

Thời gian$O(N \log(N \cdot H))$

C++▶ Chạy tay từng dòng codeTheo dõi chặt nhị phân và hai con trỏ trong từng lần gọi countLE.

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

Dữ liệu mẫu:

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

2using namespace std;

3const int MAXN = 300005;

4int n, dq[MAXN];

5long long K, h[MAXN];

6// dem so khung anh co dien tich <= X

7long long countLE(long long X) {

8 int head = 0, tail = 0, l = 0; // dq[head..tail-1]: chi so, h giam dan

9 long long cnt = 0;

10 for (int r = 0; r < n; r++) {

11 while (tail > head && h[dq[tail - 1]] <= h[r]) tail--;

12 dq[tail++] = r;

13 while (l <= r && (r - l + 1) * h[dq[head]] > X) {

14 l++;

15 if (dq[head] < l) head++;

16 }

17 cnt += r - l + 1;

18 }

19 return cnt;

20}

21int main() {

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

23 cin >> n >> K;

24 long long mx = 0;

25 for (int i = 0; i < n; i++) {

26 cin >> h[i];

27 mx = max(mx, h[i]);

28 }

29 long long lo = 1, hi = n * mx; // dap an nam trong [lo, hi]

30 while (lo < hi) {

31 long long mid = (lo + hi) / 2;

32 if (countLE(mid) >= K) hi = mid;

33 else lo = mid + 1;

34 }

35 cout << lo << "\n";

36 return 0;

37}

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 2000$, có $N = 1$, $K = 1$, $K = \frac{N(N+1)}{2}$), 9 test subtask 2 ($N \approx 3 \cdot 10^5$, $K \le 10^6$, có test mọi cây bẹo cao $10^9$ cho đáp án $4 \cdot 10^9$), 11 test subtask 3 ($N = 3 \cdot 10^5$, $K \ge 10^9$). Các dãy $h$ gồm ngẫu nhiên, tăng, giảm, bằng nhau, răng cưa, hình núi, vài "gai" rất cao.

Cách làm	Sub 1 (20%)	Sub 2 (30%)	Sub 3 (50%)	Điểm
Cách 1 – liệt kê O(N²) + nth_element	Đúng	TLE	TLE	20
Cách 2 – hàng đợi ưu tiên O((N + K) log N)	Đúng	Đúng	TLE	50
Cách 3 – chặt nhị phân + hai con trỏ + deque	Đúng	Đúng	Đúng	100
Sai 1 – biến đếm int	Đúng	WA	1/11 test	≈ 24,5
Sai 2 – cận trên hi = 2·109	4/10 test	7/9 test	2/11 test	≈ 40,4
Sai 3 – giữ max chạy, không dùng deque	7/10 test	5/9 test	6/11 test	≈ 57,9

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à quá 3 giây ở mọi test còn lại; Cách 2 đúng hết subtask 1, 2 và quá 3 giây ở mọi test subtask 3; Cách 3 đúng 30/30 test, test lâu nhất khoảng 0,22 giây CPU. Điểm của các lời giải sai được tính theo số test đúng trong từng subtask (chấm kiểu Tổng).

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 😇