Mảng hiệu
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Mảng cộng dồn 1 chiều
- Chủ đề
- cộng dồnmảng hiệu
- Trạng thái
Kiến thức cơ bản
Vì sao cần mảng hiệu
Gấu Po có một hàng n luống rau. Mỗi lần, Thỏ nhờ Gấu Po tưới thêm v lít nước cho các luống từ l đến r. Sau q lần tưới, Thỏ muốn biết mỗi luống có bao nhiêu lít nước.
Cách làm trực tiếp là với mỗi lần tưới, chạy vòng for từ l đến r để cộng v vào từng ô. Mỗi lần mất tối đa n phép cộng, q lần mất khoảng n × q phép. Với n = q = 105 ta mất khoảng 1010 phép tính, chậm hơn quy ước 108 rất nhiều (như em đã học ở tuần Độ phức tạp).
Tuần 13, mảng cộng dồn giúp ta hỏi tổng đoạn thật nhanh. Tuần này ta học "người anh em song sinh" của nó: mảng hiệu giúp ta cập nhật cả đoạn thật nhanh, mỗi lần chỉ tốn 2 phép tính.
Mảng hiệu là gì
Ý tưởng: bậc thang
Hình dung mảng a là một dãy bậc thang, bậc thứ i cao a[i] viên gạch. Thay vì ghi độ cao của từng bậc, Gấu Po ghi lại mỗi bước đi từ bậc trước sang bậc này phải bước lên hay bước xuống bao nhiêu viên. Dãy các số đó chính là mảng hiệu d:
d[i] = a[i] − a[i − 1] (quy ước a[0] = 0, nên d[1] = a[1])
5 | # #
4 | # #
3 | # # # #
2 | # # # # # #
1 | # # # # # #
0 +------------------------
1 2 3 4 5 6 7 8
a: 0 3 3 5 5 2 2 0
d: 0 +3 0 +2 0 -3 0 -2
Khôi phục mảng a từ mảng hiệu
Muốn biết bậc thứ i cao bao nhiêu, ta xuất phát từ mặt đất (độ cao 0) rồi cộng dồn tất cả các bước đã đi: a[i] = d[1] + d[2] + ... + d[i]. Đây chính là phép cộng dồn đã học ở tuần 13, chỉ cần viết d[i] += d[i − 1] cho i từ 1 đến n.
Cộng v cho cả đoạn [l, r]
Nếu nâng cả đoạn từ ô l đến ô r lên v đơn vị thì chỉ có hai bước thay đổi: bước đi vào ô l cao thêm v, và bước đi ra khỏi ô r sang ô r + 1 thấp xuống v. Các bước ở giữa vẫn như cũ vì hai ô liền nhau cùng được nâng lên như nhau. Vì vậy:
d[l] += v; d[r + 1] −= v;
Ví dụ: n = 8, mảng a ban đầu toàn số 0. Cộng 3 cho đoạn [2, 5], rồi cộng 2 cho đoạn [4, 7].
i : 1 2 3 4 5 6 7 8
d (luc dau) : 0 0 0 0 0 0 0 0
+3 cho [2, 5] : 0 +3 0 0 0 -3 0 0 d[2] += 3, d[6] -= 3
+2 cho [4, 7] : 0 +3 0 +2 0 -3 0 -2 d[4] += 2, d[8] -= 2
cong don d : 0 3 3 5 5 2 2 0 = mang a cuoi cung
Mã nguồn mẫu
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<long long> d(n + 2, 0); // dư 1 ô cho d[r + 1]
while (q--) {
int l, r;
long long v;
cin >> l >> r >> v;
d[l] += v; // đi vào ô l: cao thêm v
d[r + 1] -= v; // đi ra khỏi ô r: thấp xuống v
}
for (int i = 1; i <= n; i++) {
d[i] += d[i - 1]; // cộng dồn: d[i] giờ là giá trị thật a[i]
cout << d[i] << " ";
}
return 0;
}
Nếu mảng a đã có sẵn giá trị ban đầu, ta dựng mảng hiệu trước khi xử lý các lần cộng đoạn (a[0] = 0):
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = a[i] - a[i - 1]; // độ chênh so với ô liền trước
}
Sau đó cập nhật d[l] += v, d[r + 1] −= v như trên, rồi cộng dồn để lấy mảng cuối cùng. Độ phức tạp là O(n + q): với n = q = 105 máy tính chỉ mất một cái chớp mắt.
Các tính chất
- Mỗi lần cộng đoạn chỉ tốn O(1) (2 phép cộng), việc cộng dồn để lấy kết quả chỉ làm một lần ở cuối.
- Khi r = n, ta ghi vào d[n + 1], nên mảng hiệu cần có ít nhất n + 2 phần tử (vector<long long> d(n + 2)).
- Chỉ dùng được khi làm xong mọi lần cập nhật rồi mới xem kết quả. Nếu vừa cập nhật vừa hỏi giá trị xen kẽ thì cần công cụ mạnh hơn, em sẽ gặp ở các lớp sau.
- Giá trị cộng v có thể âm. Giá trị sau khi cộng dồn có thể rất lớn nên hãy dùng long long.
- Bài toán "đếm số lớp phủ" của một ô chính là cộng v = 1 cho mỗi đoạn: d[l]++, d[r + 1]−−.
Mảng cộng dồn và mảng hiệu
| Mảng cộng dồn (tuần 13) | Mảng hiệu (tuần 14) | |
|---|---|---|
| Công thức | s[i] = s[i − 1] + a[i] | d[i] = a[i] − a[i − 1] |
| Bài toán hợp | Mảng cho trước, hỏi nhiều lần tổng đoạn [l, r] | Cộng nhiều lần vào đoạn [l, r], chỉ cần xem mảng cuối cùng |
| Mỗi thao tác | Trả lời tổng: s[r] − s[l − 1] | Cập nhật: d[l] += v; d[r + 1] −= v |
| Quan hệ | Cộng dồn của mảng hiệu cho lại mảng gốc | Hiệu của mảng cộng dồn cho lại mảng gốc |
Hai công cụ này hay đi cùng nhau: dùng mảng hiệu để làm xong mọi lần cập nhật, rồi dùng mảng cộng dồn để trả lời các câu hỏi về tổng đoạn.
Mở rộng (không bắt buộc): cộng dồn 2 chiều
Với bảng a có n hàng, m cột, đặt s[i][j] là tổng tất cả các ô nằm trong hình chữ nhật từ ô (1, 1) đến ô (i, j). Có thể tính dần từng ô:
s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
Ô s[i − 1][j − 1] bị cộng hai lần (một lần trong s[i − 1][j], một lần trong s[i][j − 1]) nên phải trừ đi một lần. Để tính tổng hình chữ nhật có góc trên trái (x1, y1) và góc dưới phải (x2, y2), ta lấy hình lớn rồi trừ hai miếng thừa và cộng lại miếng bị trừ hai lần:
long long sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
Nhớ khai báo s với cỡ (n + 1) × (m + 1) và dùng long long.
Luyện tập
Bài 1. Bậc thang của Gấu Po
Gấu Po xây một dãy n bậc thang bằng gạch, bậc thứ i cao a[i] viên. Thỏ muốn ghi lại "độ chênh" của từng bậc so với bậc liền trước nó: d[i] = a[i] − a[i − 1], trong đó bậc số 0 coi như cao 0 viên. Em hãy giúp Thỏ lập mảng d nhé.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên d[1], d[2], ..., d[n], cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 2 5 5 1 4 | 2 3 0 -4 3 |
| 2 | 3 7 7 7 | 7 0 0 |
Bài 2. Giải mã bậc thang
Hổ nhặt được cuốn sổ ghi mảng hiệu d của dãy bậc thang (d[i] cho biết bậc i cao hơn hay thấp hơn bậc i − 1 bao nhiêu viên gạch, bậc số 0 cao 0). Hổ muốn biết độ cao thật a[i] của từng bậc. Hãy giải mã giúp Hổ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên d[i] (|d[i]| ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên a[1], a[2], ..., a[n], cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 2 3 0 -4 3 | 2 5 5 1 4 |
| 2 | 4 1000000000 1000000000 1000000000 0 | 1000000000 2000000000 3000000000 3000000000 |
Bài 3. Tưới hàng cây
Vườn của Gấu Po có n cây xếp thành hàng, ban đầu cây nào cũng chưa có giọt nước nào. Gấu Po tưới q lần, mỗi lần tưới một đoạn các cây liên tiếp từ cây l đến cây r và mỗi cây trong đoạn nhận thêm 1 lít nước. Hỏi sau q lần tưới, mỗi cây có bao nhiêu lít nước?
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | n số nguyên, số thứ i là lượng nước của cây i, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 3 1 3 2 5 4 6 | 1 2 2 2 2 1 |
| 2 | 4 1 1 4 | 1 1 1 1 |
Bài 4. Cộng điểm thưởng
Lớp của Thỏ có n bạn, bạn thứ i đang có a[i] điểm. Cô giáo thực hiện q lần: cộng v điểm cho tất cả các bạn từ bạn l đến bạn r (v âm nghĩa là trừ điểm). Hãy cho biết điểm cuối cùng của mỗi bạn.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). q dòng tiếp theo: mỗi dòng gồm ba số nguyên l, r, v (1 ≤ l ≤ r ≤ n; |v| ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên là điểm cuối cùng của từng bạn, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 3 4 8 1 6 3 1 3 2 2 5 -1 4 4 10 | 6 9 2 15 2 |
| 2 | 3 2 1000000000 -1000000000 5 1 3 1000000000 2 3 1000000000 | 2000000000 1000000000 2000000005 |
Bài 5. Hàng rào chưa sơn
Hổ có một hàng rào gồm n tấm ván đánh số từ 1 đến n. Hổ đã sơn q lần, mỗi lần sơn các tấm ván liên tiếp từ l đến r (tấm nào đã sơn rồi thì sơn chồng lên). Hỏi còn bao nhiêu tấm ván chưa được sơn lần nào?
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n ≤ 106; 1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Số tấm ván chưa được sơn lần nào. | |
| Test | Input | Output |
| 1 | 10 3 2 4 3 6 9 9 | 4 |
| 2 | 5 1 1 5 | 0 |
Bài 6. Lớp thảm dày nhất
Hành lang nhà Gấu Po dài n ô. Gấu Po trải m tấm thảm, tấm thảm thứ i phủ các ô từ l đến r (các tấm thảm có thể chồng lên nhau). Gấu Po muốn biết: có ô nào bị chồng nhiều lớp thảm nhất là bao nhiêu lớp, và có bao nhiêu ô đạt đúng số lớp nhiều nhất đó?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n ≤ 106; 1 ≤ m ≤ 105). m dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Hai số nguyên cách nhau một dấu cách: số lớp thảm nhiều nhất trên một ô và số ô đạt số lớp đó. | |
| Test | Input | Output |
| 1 | 8 3 1 4 3 6 4 8 | 3 1 |
| 2 | 5 2 1 2 4 5 | 1 4 |
Bài 7. Ngày trực đủ người
Học kỳ có n ngày, đánh số từ 1 đến n. Có m bạn đăng ký trực lớp, bạn thứ i trực liên tục từ ngày l đến ngày r. Cô giáo cần mỗi ngày có ít nhất K bạn trực. Hỏi có bao nhiêu ngày đạt yêu cầu đó?
| Đầu vào | Dòng 1: ba số nguyên n, m, K (1 ≤ n ≤ 106; 1 ≤ m ≤ 105; 1 ≤ K ≤ m). m dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Số ngày có ít nhất K bạn trực. | |
| Test | Input | Output |
| 1 | 10 4 2 1 5 3 8 4 6 7 10 | 6 |
| 2 | 6 2 3 1 6 2 5 | 0 |
Bài 8. Tưới xong rồi hỏi
Thỏ trồng n cây, ban đầu cây nào cũng có 0 lít nước. Thỏ tưới q lần, mỗi lần đổ thêm v lít nước cho mỗi cây từ cây l đến cây r. Sau khi tưới xong tất cả, Gấu Po hỏi p câu: "Tổng lượng nước của các cây từ cây l đến cây r là bao nhiêu?". Em hãy giúp Thỏ trả lời.
| Đầu vào | Dòng 1: ba số nguyên n, q, p (1 ≤ n, q, p ≤ 105). q dòng tiếp theo: mỗi dòng gồm ba số nguyên l, r, v (1 ≤ l ≤ r ≤ n; 1 ≤ v ≤ 104). p dòng cuối: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n) là một câu hỏi. | |
|---|---|---|
| Đầu ra | p dòng, mỗi dòng là câu trả lời của một câu hỏi theo đúng thứ tự. | |
| Test | Input | Output |
| 1 | 5 2 3 1 3 2 2 5 1 1 5 2 3 5 5 | 10 6 1 |
| 2 | 3 1 2 1 3 10000 1 1 1 3 | 10000 30000 |
Bài 9. Xếp hạng sau thưởng
Có n bạn đánh số từ 1 đến n tham gia trò chơi, bạn thứ i đang có a[i] điểm. Gấu Po phát thưởng q lần: lần thứ j cộng v điểm cho các bạn từ bạn l đến bạn r (v có thể âm). Sau tất cả, hãy xếp hạng các bạn từ điểm cao xuống điểm thấp; hai bạn bằng điểm thì bạn có số thứ tự nhỏ hơn đứng trước.
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n, q ≤ 105). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). q dòng tiếp theo: mỗi dòng gồm ba số nguyên l, r, v (1 ≤ l ≤ r ≤ n; |v| ≤ 109). | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng gồm số thứ tự của bạn và điểm cuối cùng của bạn đó, cách nhau một dấu cách, theo đúng thứ tự xếp hạng. | |
| Test | Input | Output |
| 1 | 5 2 10 20 30 40 50 1 3 15 2 5 -5 | 5 45 3 40 4 35 2 30 1 25 |
| 2 | 3 1 7 7 7 2 2 1 | 2 8 1 7 3 7 |
Bài tập tự luyện
Bài 1. Hoa nở đúng K lần
Vườn nhà Thỏ có n luống hoa. Thỏ rải phân bón q lần, mỗi lần rải đều lên các luống từ l đến r. Thỏ biết loại hoa này chỉ nở đẹp nếu luống đó được bón đúng K lần (không nhiều hơn, không ít hơn). Hỏi có bao nhiêu luống nở đẹp?
| Đầu vào | Dòng 1: ba số nguyên n, q, K (1 ≤ n ≤ 106; 1 ≤ q ≤ 105; 0 ≤ K ≤ q). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Số luống được bón đúng K lần. | |
| Test | Input | Output |
| 1 | 8 3 2 1 4 3 6 4 8 | 3 |
| 2 | 5 1 0 2 3 | 3 |
Bài 2. Hai đội cùng tưới
Có n luống rau xếp hàng. Đội của Gấu Po tưới p đoạn, đội của Hổ tưới h đoạn (mỗi đoạn là các luống liên tiếp từ l đến r). Hãy đếm xem có bao nhiêu luống được cả hai đội cùng tưới (mỗi đội tưới luống đó ít nhất một lần).
| Đầu vào | Dòng 1: ba số nguyên n, p, h (1 ≤ n ≤ 106; 1 ≤ p, h ≤ 105). p dòng tiếp theo: mỗi dòng là một đoạn l, r của đội Gấu Po. h dòng cuối: mỗi dòng là một đoạn l, r của đội Hổ. (1 ≤ l ≤ r ≤ n) | |
|---|---|---|
| Đầu ra | Số luống được cả hai đội tưới. | |
| Test | Input | Output |
| 1 | 10 2 2 1 4 3 5 2 3 5 8 | 3 |
| 2 | 6 1 1 1 2 4 6 | 0 |
Bài 3. Khoảng trống dài nhất
Một con đường có n ô vuông. Hổ đã lát gạch q lần, mỗi lần lát các ô liên tiếp từ l đến r. Gấu Po muốn tìm đoạn gồm các ô liên tiếp chưa được lát viên gạch nào mà dài nhất để dựng quán nước. Đoạn đó dài bao nhiêu ô?
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n ≤ 106; 1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). | |
|---|---|---|
| Đầu ra | Độ dài lớn nhất của đoạn liên tiếp các ô chưa được lát. Nếu không còn ô nào trống thì in 0. | |
| Test | Input | Output |
| 1 | 12 3 2 3 6 6 9 10 | 2 |
| 2 | 4 2 1 2 3 4 | 0 |
Bài 4. Bạn đạt chuẩn
Lớp có n bạn, bạn thứ i đang có a[i] điểm rèn luyện. Cô giáo cộng hoặc trừ điểm theo q lần: lần thứ j cộng v điểm cho các bạn từ bạn l đến bạn r (v có thể âm). Một bạn được khen thưởng nếu điểm cuối cùng của bạn đó từ X trở lên. Có bao nhiêu bạn được khen thưởng?
| Đầu vào | Dòng 1: ba số nguyên n, q, X (1 ≤ n, q ≤ 105; |X| ≤ 1014). Dòng 2: n số nguyên a[i] (|a[i]| ≤ 109). q dòng tiếp theo: mỗi dòng gồm ba số nguyên l, r, v (1 ≤ l ≤ r ≤ n; |v| ≤ 109). | |
|---|---|---|
| Đầu ra | Số bạn có điểm cuối cùng không nhỏ hơn X. | |
| Test | Input | Output |
| 1 | 5 3 10 4 8 1 6 3 1 3 5 2 5 -1 4 4 4 | 1 |
| 2 | 3 2 3000000000 1000000000 1000000000 1000000000 1 3 1000000000 2 3 1000000000 | 2 |
Bài 5. Bậc thang đủ cao
Gấu Po xây một dãy n cột gạch, ban đầu cột nào cũng cao 0 viên. Mỗi lần xây, Gấu Po chọn một cột l rồi thêm v viên gạch cho cột l và tất cả các cột bên phải nó (từ cột l đến cột n). Sau khi xây xong q lần, Thỏ hỏi p câu: "Cột đầu tiên (từ trái sang) có chiều cao ít nhất x là cột nào?". Em hãy trả lời giúp.
| Đầu vào | Dòng 1: ba số nguyên n, q, p (1 ≤ n, q, p ≤ 105). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, v (1 ≤ l ≤ n; 1 ≤ v ≤ 104). p dòng cuối: mỗi dòng là một số nguyên x (1 ≤ x ≤ 1014). | |
|---|---|---|
| Đầu ra | p dòng, mỗi dòng in chỉ số của cột đầu tiên có chiều cao ít nhất x, hoặc in -1 nếu không có cột nào. | |
| Test | Input | Output |
| 1 | 6 3 4 2 3 5 4 3 1 1 4 7 9 | 2 3 5 -1 |
| 2 | 3 1 2 2 5 5 6 | 2 -1 |
Bài 6. Chuyến xe buýt
Tuyến xe buýt của Hổ có n bến, đánh số từ 1 đến n. Có m hành khách, khách thứ i lên xe ở bến l và xuống xe ở bến r (l < r). Khi xe đến một bến thì khách xuống trước, sau đó khách mới mới lên, nên hai khách [1, 3] và [3, 5] có thể ngồi chung một ghế. Hỏi xe cần ít nhất bao nhiêu ghế để mọi khách đều có chỗ ngồi?
| Đầu vào | Dòng 1: hai số nguyên n, m (2 ≤ n ≤ 106; 1 ≤ m ≤ 105). m dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l < r ≤ n). | |
|---|---|---|
| Đầu ra | Số ghế ít nhất cần dùng. | |
| Test | Input | Output |
| 1 | 5 3 1 3 3 5 2 4 | 2 |
| 2 | 4 2 1 2 2 4 | 1 |
Bài 7. Tổng hình chữ nhật (không bắt buộc)
Thỏ có một bảng ô vuông gồm n hàng, m cột, ô ở hàng i, cột j chứa số a[i][j]. Gấu Po hỏi q câu, mỗi câu cho hai ô góc (x1, y1) và (x2, y2) của một hình chữ nhật (x1 ≤ x2, y1 ≤ y2). Hãy tính tổng các số nằm trong hình chữ nhật đó. Gợi ý: dùng mảng cộng dồn 2 chiều.
| Đầu vào | Dòng 1: ba số nguyên n, m, q (1 ≤ n, m ≤ 1000; 1 ≤ q ≤ 105). n dòng tiếp theo: mỗi dòng gồm m số nguyên a[i][j] (|a[i][j]| ≤ 109). q dòng cuối: mỗi dòng gồm bốn số nguyên x1, y1, x2, y2. | |
|---|---|---|
| Đầu ra | q dòng, mỗi dòng là tổng của một hình chữ nhật. | |
| Test | Input | Output |
| 1 | 3 4 2 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 2 2 2 3 4 | 14 54 |
| 2 | 2 2 1 1000000000 1000000000 1000000000 1000000000 1 1 2 2 | 4000000000 |
Bài 8. Thợ sơn dư thừa
Hổ thuê q thợ sơn một hàng rào gồm n tấm ván, thợ thứ i sơn các tấm ván từ l đến r. Biết rằng nếu cả q thợ cùng làm thì tấm ván nào cũng được sơn ít nhất một lần. Hổ muốn đuổi bớt đúng một thợ mà hàng rào vẫn được sơn kín hoàn toàn. Hỏi có bao nhiêu thợ mà nếu đuổi riêng người đó thì hàng rào vẫn được sơn kín?
| Đầu vào | Dòng 1: hai số nguyên n, q (1 ≤ n ≤ 106; 1 ≤ q ≤ 105). q dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l ≤ r ≤ n). Dữ liệu đảm bảo mọi tấm ván đều được sơn ít nhất một lần. | |
|---|---|---|
| Đầu ra | Số thợ có thể đuổi (đuổi riêng người đó thì hàng rào vẫn kín). | |
| Test | Input | Output |
| 1 | 6 4 1 3 2 4 4 6 3 5 | 2 |
| 2 | 5 3 1 5 1 2 3 5 | 3 |
Bài 9. Thử thách: Xếp gạch ít lần nhất
Hổ muốn xây n cột gạch, cột thứ i phải cao đúng b[i] viên. Ban đầu mọi cột cao 0 viên. Mỗi lần xây, Hổ chọn một đoạn các cột liên tiếp và thêm đúng 1 viên gạch cho mỗi cột trong đoạn đó. Hỏi Hổ cần xây ít nhất bao nhiêu lần để được đúng chiều cao yêu cầu? Gợi ý: nhìn vào mảng hiệu của b.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên b[i] (0 ≤ b[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số lần xây ít nhất. | |
| Test | Input | Output |
| 1 | 5 2 3 1 1 4 | 6 |
| 2 | 3 5 5 5 | 5 |
- Gợi ý chung: (1) Mảng hiệu luôn khai báo cỡ n + 2 vì có lúc phải ghi vào d[r + 1]. (2) Mọi bài cộng nhiều lần đều nên dùng long long. (3) Đừng quên bước cộng dồn cuối cùng để biến mảng hiệu thành mảng thật. (4) Bài đếm số lớp phủ: mỗi đoạn là d[l]++, d[r + 1]−−, sau khi cộng dồn thì d[i] là số đoạn phủ ô i. (5) Đọc kỹ đề xem đoạn là [l, r] hay [l, r − 1] (bài xe buýt): khách xuống ở bến r thì ghế đã trống từ bến r.