Tăng Đầu Giảm Cuối (ARRAYM)

Nguồn: LuyenCode Độ khó: Trung bình Prefix sum Mảng hiệu Truy vấn đoạn

Đề bài

ARRAYM – Tăng đầu giảm cuối

Cho một dãy số $a_1, a_2, \ldots, a_n$, ban đầu $a_i = 0\ \forall i = 1..n$ và $m$ truy vấn dạng $Q(u, v, k)$ tương ứng tăng các giá trị $a_u, a_{u+1}, \ldots, a_v$ lên một lượng bằng $k$.

Ví dụ: Cho dãy $a = [0, 0, 0]$, sau truy vấn $Q(2, 3, 30)$ thì dãy $a$ trở thành $a = [0, 30, 30]$.

Yêu cầu: Sau $m$ truy vấn, hãy tìm giá trị lớn nhất của dãy $a$.

Dữ liệu vào:

• Dòng đầu ghi hai số nguyên dương $n, m$ $(3 \le n \le 10^7;\ 1 \le m \le 2 \times 10^5)$;
• $m$ dòng tiếp theo, dòng thứ $i$ ghi truy vấn $i$ gồm ba số nguyên không âm $u, v, k$ $(1 \le u \le v \le n;\ 0 \le k \le 10^9)$.

Dữ liệu ra:

• Ghi ra một số nguyên duy nhất là giá trị lớn nhất của dãy $a$ sau $m$ truy vấn.

Ví dụ – input

5 3
1 2 100
2 5 100
3 4 100

Ví dụ – output

200

Gợi ý (của đề):

• Dãy ban đầu: $a = [0, 0, 0, 0, 0]$;
• Truy vấn 1: $a = [100, 100, 0, 0, 0]$;
• Truy vấn 2: $a = [100, 200, 100, 100, 100]$;
• Truy vấn 3: $a = [100, 200, 200, 200, 100]$.

Giá trị lớn nhất là $200$.

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước khi vào bài, các bạn nhớ lại ngưỡng an toàn mình hay nhắc: với các hệ thống chấm giới hạn 1 giây thì toàn bài chỉ nên lặp khoảng $(3 \div 5) \cdot 10^7$ lần (C/C++), cao lắm là $10^8$ thì hên xui; Python, Java, C# chạy chậm hơn nên ngưỡng còn thấp hơn nữa. Ta không cần đếm chi tiết từng phép toán mà cứ canh theo số lần các vòng lặp chạy. Bài này mình tính theo giới hạn chuẩn 1 giây.

Đề bài đã giải thích rất kỹ và cho ví dụ mẫu kèm giải thích từng bước mảng biến đổi ra sao (phần Gợi ý ở trên) nên mình không giải thích thêm nhé. Bạn nào đọc đề vẫn chưa rõ thì đọc thật kỹ lại phần Gợi ý, đối chiếu từng truy vấn là hiểu ngay.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn từng đoạn · O(N + M·N) · TLECách 2Mảng hiệu + cộng dồn · O(N + M)

Cách 1Vét cạn: cộng k vào từng phần tử của đoạn – O(N + M·N)

Cách cơ bản nhất nhìn thấy ngay: với mỗi truy vấn, ta chạy vòng lặp xét từng phần tử trong đoạn từ $u$ đến $v$ và tăng mỗi phần tử thêm $k$. Làm đủ $m$ truy vấn rồi duyệt lại mảng từ đầu đến cuối tìm Max và in ra.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 1, 0);
    while(m--){
        int u, v, k;
        cin >> u >> v >> k;
        for(int i = u; i <= v; ++i){
            a[i] += k;
        }
    }
    long long Max = a[1];
    for(int i = 2; i <= n; ++i){
        Max = max(Max, a[i]);
    }
    cout << Max;
    return 0;
}

import sys

data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] * (n + 1)
p = 2
for _ in range(m):
    u, v, k = int(data[p]), int(data[p + 1]), int(data[p + 2])
    p += 3
    for i in range(u, v + 1):
        a[i] += k
Max = a[1]
for i in range(2, n + 1):
    Max = max(Max, a[i])
print(Max)

Giải thích một số chỗ trong code ở trên:

1. Vị trí trong đề luôn tính từ $1$, nên để thống nhất ta khởi tạo mảng a có $n + 1$ phần tử, chỉ số từ $1$ đến $n$, bỏ qua không dùng ô $0$. Chứ nếu chỉ có $n$ phần tử (chỉ số $0..n-1$) thì mỗi lần xét đoạn $u..v$ lại phải hiểu là $u-1..v-1$, dễ bị rối lắm. Cho dư 1 ô chẳng mất bao nhiêu bộ nhớ mà tránh bị rối.
2. Mảng a kiểu số nguyên 8 byte (long long) cho chắc: $k$ tối đa $10^9$, chỉ cần 2 lần $10^9$ cộng lại đã là $2 \cdot 10^9$, tiệm cận giới hạn kiểu int 4 byte rồi, nhiều hơn là tràn luôn. Tối đa $m = 2 \cdot 10^5$ truy vấn nên mỗi vị trí có thể lên tới $2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}$, kiểu long long (tối đa $2^{63} - 1 \approx 9 \cdot 10^{18}$) vẫn chứa thoải mái.
3. Bước so sánh, cập nhật Max dùng hàm max(a, b) có sẵn trong C++ cho gọn – nó trả về số lớn hơn trong 2 số.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng a.
• Thời gian: $O(N)$ khởi tạo mảng toàn số 0, cộng $O(M \cdot (V - U))$ cho các truy vấn, cộng $O(N)$ duyệt tìm Max. Theo quy tắc cộng Big-O lấy thành phần lớn nhất: $O(\max(N, M \cdot (V - U)))$.

Không gian$O(N)$

Thời gian$O(N + M \cdot N)$

TLE chắc chắn

Trường hợp xấu nhất $N = 10^7$, $M = 2 \cdot 10^5$ và mọi truy vấn đều là cả mảng ($U = 1$, $V = 10^7$): tổng số lần lặp là $10^7 + 2 \cdot 10^5 \cdot 10^7 + 10^7 = 2\,000\,020\,000\,000$ (2 nghìn tỷ 20 triệu) lần. Quá kinh khủng, vượt xa ngưỡng $(3 \div 5) \cdot 10^7$ ⇒ chắc chắn TLE. Mình chạy thử bản C++ với test này: sau 10 giây vẫn chưa xong.

Tuy vậy ta vẫn nên làm nó, để lấy làm công cụ kiểm tra tính chính xác cho cách tối ưu ở sau. Vét cạn chỉ chạy chậm thôi chứ kết quả luôn chính xác (dĩ nhiên phải cài đặt đúng, nhưng vét cạn thì khó mà cài sai).

Cách 2Mảng hiệu + cộng dồn (Prefix Sum) – O(N + M)

Bài này thực ra là một dạng kinh điển của kỹ thuật Prefix Sum (mảng cộng dồn), bài toán "tăng giá trị các đoạn": cho mảng $A$ có $N$ phần tử, nhiều truy vấn, mỗi truy vấn tăng các phần tử trong đoạn $[Left, Right]$ lên $K$; hỏi sau tất cả các truy vấn mảng $A$ thế nào. Bạn nào chưa biết công thức thì khó lòng làm được lắm. Mình nói luôn công thức, chạy tay với ví dụ của đề, rồi cuối cùng giải thích vì sao nó đúng.

Công thức 4 bước

1. Bước 1: khởi tạo mảng $B$ có $N$ phần tử, tất cả bằng $0$.
2. Bước 2: với mỗi truy vấn $(Left, Right, K)$: B[Left] += K đồng thời B[Right + 1] -= K. Làm như thế với tất cả truy vấn.
3. Bước 3: biến $B$ thành mảng cộng dồn từ đầu về cuối: $B[1]$ giữ nguyên, B[2] += B[1], B[3] += B[2], ..., B[N] += B[N-1].
4. Bước 4: A[i] += B[i] với mọi $i$ – lúc này $A$ chính là mảng sau khi thực hiện đủ các truy vấn.

Áp dụng ngay vào ví dụ của đề ($N = 5$, 3 truy vấn):

Bước	B[1]	B[2]	B[3]	B[4]	B[5]	Ghi chú
Bước 1	0	0	0	0	0	mảng toàn 0
Q(1, 2, 100)	100	0	−100	0	0	B[1] += 100, B[3] −= 100
Q(2, 5, 100)	100	100	−100	0	0	B[2] += 100, B[6] nằm ngoài mảng nên khỏi xử lý
Q(3, 4, 100)	100	100	0	0	−100	B[3] += 100, B[5] −= 100
Bước 3 (cộng dồn)	100	200	200	200	100	giống hệt đáp án của đề!

Bước 4: mảng $A$ ban đầu toàn $0$ nên cộng với $B$ thì $A$ cũng chính là $\{100, 200, 200, 200, 100\}$ – y như phần Gợi ý của đề. Duyệt tìm Max được $200$ ✔.

Bài này bỏ được bước 1 và bước 4

Vì mảng $A$ ban đầu toàn số $0$ nên sau bước 4, $A$ vẫn chính là $B$. Tức là không cần tạo thêm mảng $B$, cứ dùng luôn mảng a làm $B$. Còn những bài mà mảng ban đầu có giá trị khác $0$ thì phải làm đủ quy trình 4 bước nhé.

Cẩn thận ô Right + 1

Trên lý thuyết $B$ có $N$ phần tử, nhưng khi cài đặt ta bỏ ô $0$ nên cần $N + 1$ ô. Khi $Right = N$ thì B[Right + 1] là B[N + 1] – đi vào vùng nhớ không hợp lệ, có thể văng lỗi. Hoặc ta xét điều kiện Right + 1 > N thì bỏ qua (như lúc chạy tay truy vấn 2 ở trên), hoặc cho gọn: khai báo luôn $N + 2$ ô, có thêm ô $N + 1$ gọi tới thoải mái, đằng nào cuối cùng cũng không dùng đến.

Em nhập $n$ và các truy vấn (mỗi truy vấn 3 số $u\ v\ k$, cách nhau bởi dấu ;) rồi bấm Tiếp để xem từng truy vấn chỉ "đánh dấu" 2 đầu mút, sau đó cộng dồn ra đúng mảng $A$. Dòng cuối là mảng $A$ tính kiểu vét cạn để các bạn đối chiếu:

n Truy vấn u v k

Ví dụ nhanh:

Trong code, mình tận dụng luôn: vừa cộng dồn tới đâu thì so sánh tìm Max tới đó, khỏi chạy thêm một vòng lặp riêng. Source code để các bạn tham khảo nếu làm theo hướng này:

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<long long> a(n + 2, 0);
    while(m--){
        int u, v, k;
        cin >> u >> v >> k;
        a[u] += k;
        a[v + 1] -= k;
    }
    long long Max = a[1];
    for(int i = 2; i <= n; ++i){
        a[i] += a[i - 1];
        Max = max(Max, a[i]);
    }
    cout << Max;
    return 0;
}

import sys
from itertools import accumulate

data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
a = [0] * (n + 2)
p = 2
for _ in range(m):
    u, v, k = int(data[p]), int(data[p + 1]), int(data[p + 2])
    p += 3
    a[u] += k
    a[v + 1] -= k
# cộng dồn a[1..n] rồi lấy max (accumulate chạy nhanh hơn vòng for thường)
print(max(accumulate(a[1:n + 1])))

Bấm Tiếp để chạy tay từng dòng code:

C++▶ Chạy tay từng dòng codeCách 2: mỗi truy vấn chỉ sửa a[u] và a[v + 1], cuối cùng cộng dồn và tìm Max.

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

Dữ liệu mẫu:

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

2using namespace std;

3

4int main(){

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

7 int n, m;

8 cin >> n >> m;

9 vector<long long> a(n + 2, 0);

10 while(m--){

11 int u, v, k;

12 cin >> u >> v >> k;

13 a[u] += k;

14 a[v + 1] -= k;

15 }

16 long long Max = a[1];

17 for(int i = 2; i <= n; ++i){

18 a[i] += a[i - 1];

19 Max = max(Max, a[i]);

20 }

21 cout << Max;

22 return 0;

23}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(N)$ cho mảng a.
• Thời gian: $O(M)$ xử lý các truy vấn (mỗi truy vấn đúng 2 phép, dù đoạn $[u, v]$ dài cỡ nào) cộng $O(N)$ cộng dồn và tìm Max ⇒ $O(\max(M, N))$, hay viết $O(N + M)$.

Không gian$O(N)$

Thời gian$O(N + M)$

Cùng trường hợp xấu nhất như ở cách 1 ($N = 10^7$, $M = 2 \cdot 10^5$, mọi đoạn là cả mảng), giờ chỉ còn $2 \cdot 10^5 + 10^7 = 10\,200\,000$ (10 triệu 200 ngàn) lần lặp – còn cách ngưỡng 1 giây từ 3 đến 10 lần, yên tâm không TLE. Từ 2 nghìn tỷ lần rút xuống còn 10 triệu, các bạn đã thấy cái hay của giải thuật rồi chứ 😆?

Đừng khai báo mảng 10^7 phần tử trong hàm main

Bản gốc trên Facebook mình viết long long a[n + 2] = {0}; ngay trong main. Mảng này cỡ $8 \cdot 10^7$ byte = 80 MB nằm trên stack, mà stack mặc định thường chỉ có 8 MB – mình chạy thử với $n = 10^7$ thì bị lỗi Segmentation fault (Runtime Error) ngay. Nên code ở trên mình đổi sang vector<long long> a(n + 2, 0) (cấp phát trên heap); khai báo mảng toàn cục long long a[10000002]; bên ngoài main cũng được. Logic thì giữ nguyên.

Vì sao công thức này đúng?

Với công thức này, mỗi đoạn $[Left, Right]$ ta không cần chạy từ $Left$ đến $Right$ để cộng từng phần tử, mà chỉ xử lý 2 đầu mút; đoạn có rộng tới đâu cũng chỉ 2 phép. Phải công nhận công thức này bá đạo quá các bạn nhỉ? Mình thừa nhận là lần đầu gặp dạng bài này mình cũng chẳng nhìn ra được đâu, sau đó được học rồi mới biết, nay mình chia sẻ lại cho các bạn 😁.

• B[Left] += K là đặt đầu mút bắt đầu. Khi cộng dồn, giá trị $K$ này được "truyền" sang tất cả các ô từ $Left$ trở về sau, nên mọi ô từ $Left$ trở đi đều tăng đúng $K$.
• B[Right + 1] -= K là đặt đầu mút kết thúc. Cộng dồn tới ô $Right$ thì vẫn còn $+K$, nhưng sang ô $Right + 1$ thì gặp $-K$, bù trừ lại về như cũ. Từ đó trở đi $+K$ và $-K$ triệt tiêu nhau, không làm thay đổi các ô $Right + 2, Right + 3, \ldots$ nữa.

Nói thì sợ các bạn khó hình dung, các bạn cứ lấy giấy ra tự cho một mảng và vài truy vấn, áp dụng công thức rồi cộng dồn (hoặc bấm khung minh hoạ ở trên với dữ liệu tự chọn) là sẽ nghiệm ra ngay vì sao cuối cùng nó ra kết quả đúng hehe.

Về bản Python

Với $n = 10^7$, một vòng for thường trong Python chạy rất chậm, nên bản Python mình dùng itertools.accumulate để cộng dồn và hàm max có sẵn; đọc dữ liệu một lần bằng sys.stdin.buffer. Dù vậy với test lớn nhất nó vẫn mất khoảng 1,3–1,5 giây trên máy mình, nên nếu hệ thống chấm không nới thời gian cho Python thì có thể bị TLE – các bạn ưu tiên nộp C++ nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách đã được kiểm tra với 400 bộ test ngẫu nhiên nhỏ (có cả $k = 0$ và $k = 10^9$), so với code vét cạn – khớp hết. Với test lớn nhất $n = 10^7$, $m = 2 \cdot 10^5$ (mọi truy vấn là cả mảng, $k = 10^9$, đáp án $2 \cdot 10^{14}$): cách 2 bản C++ chạy khoảng 0,2 giây, bản Python khoảng 1,3–1,5 giây; cách 1 bản C++ sau 10 giây vẫn chưa xong ⇒ TLE đúng như phân tích.

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 😇