Chia dãy (Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B, C1, C2)

Nguồn: Tin học trẻ 2025 – Vòng loại quốc gia đợt 2 Độ khó: Khó Cây phân đoạn Quy hoạch động Mảng hiệu

Đề bài

Alice có dãy $A = (a_1, a_2, \ldots, a_n)$. Với một đoạn liên tiếp của dãy, Alice muốn chia nó thành một số đoạn con liên tiếp (mỗi phần tử thuộc đúng một đoạn con) sao cho tổng giá trị các đoạn con lớn nhất. Giá trị của một đoạn con là hiệu giữa phần tử lớn nhất và phần tử nhỏ nhất của nó.

Alice phải xử lí $Q$ thao tác, mỗi thao tác thuộc một trong hai loại:

1. 1 l r x: cộng thêm $x$ vào mọi phần tử $a_i$ với $l \le i \le r$.
2. 2 l r: xét dãy $a_l, a_{l+1}, \ldots, a_r$ (giá trị hiện tại), tìm cách chia dãy này thành các đoạn con liên tiếp để tổng giá trị lớn nhất, in ra tổng đó.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên dương $n, Q$ $(n, Q \le 2 \cdot 10^5)$.
• Dòng thứ hai chứa $n$ số nguyên $a_1, \ldots, a_n$ $(|a_i| \le 10^6)$.
• $Q$ dòng tiếp theo, mỗi dòng là một thao tác như trên; luôn có $1 \le l \le r \le n$ và $|x| \le 10^6$.

Kết quả: với mỗi thao tác loại 2 (theo thứ tự), in ra trên một dòng tổng giá trị lớn nhất.

Subtask:

• Subtask 1 (25%): $n \le 20$, $Q = 1$.
• Subtask 2 (25%): $n, Q \le 200$.
• Subtask 3 (25%): $n, Q \le 3000$.
• Subtask 4 (25%): không có ràng buộc gì thêm.

Giới hạn thời gian: 1 giây, bộ nhớ: 1024 MB. Dữ liệu nhập từ bàn phím và in ra màn hình.

Ví dụ – input

4 3
1 2 3 4
2 1 4
1 1 1 2
2 1 4

Ví dụ – output

3
2

Giải thích:

• Thao tác 1: dãy là 1 2 3 4, để nguyên một đoạn, giá trị $4 - 1 = 3$.
• Thao tác 2 cộng 2 vào $a_1$, dãy thành 3 2 3 4. Thao tác 3: chia thành 3 2 | 3 4, tổng giá trị $(3 - 2) + (4 - 3) = 2$.

Nguồn: Hội thi Tin học trẻ toàn quốc 2025 – Vòng loại quốc gia đợt 2 – Bảng B, C1, C2. Đề bài được mình viết lại bằng lời của mình cho dễ hiểu, giữ nguyên ý nghĩa và số liệu.

Lời mở đầu

Bài này là bài "phân loại" của vòng loại đợt 2: subtask 1, 2 làm được bằng vét cạn và quy hoạch động quen thuộc, nhưng để qua $2 \cdot 10^5$ thao tác cần một nhận xét toán học đẹp (đưa bài toán về mảng hiệu) và một cây phân đoạn mà mỗi nút lưu một "ma trận" nhỏ 2×2. Mình sẽ đi từng bước, mỗi bước ăn thêm một subtask.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

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:

Bộ test20 testCách 1vét cạnCách 2QHĐ O(len²)Nhận xétmảng hiệuCách 3QHĐ O(len)Cách 4cây phân đoạn

Bộ testBộ test có gì?

Bộ test mình dùng có 20 test, mỗi subtask 5 test (test 6 là ví dụ của đề). Mình đã kiểm tra: test 1–5 có $n \le 20$, $Q = 1$; test 6–10 có $n, Q \le 200$; test 11–15 có $n, Q \le 3000$; test 16–20 có $n = Q = 2 \cdot 10^5$.

Nhóm	Test	$n$ lớn nhất	$Q$ lớn nhất	Số thao tác loại 1 / loại 2	$a_i$ ban đầu	$|x|$ lớn nhất	Đáp án lớn nhất
Subtask 1	1–5	20	1	0 / 5	-1.000.000 … 1.000.000	0	20.000.000
Subtask 2	6–10	200	200	394 / 409	-995.099 … 997.883	1.000.000	136.349.743
Subtask 3	11–15	3.000	3.000	7.481 / 7.519	-1.000.000 … 1.000.000	1.000.000	4.113.000.000
Subtask 4	16–20	200.000	200.000	299.930 / 700.070	-1.000.000 … 1.000.000	1.000.000	274.939.000.000

• Đáp án lớn tới cỡ $2{,}7 \cdot 10^{11}$ (sau nhiều thao tác cộng, $|a_i|$ có thể vượt xa $10^6$) – bắt buộc dùng long long.
• Có test chỉ có truy vấn loại 2 (test 18, 20), test giá trị nhỏ trong $[-2, 2]$ (nhiều hiệu bằng 0), test dãy hằng (đáp án 0), test $n = 1$.

Lời giải cuối cùng (cách 4) mình đã nộp thử trên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được AC (100 điểm). Kết quả chạy thật các cách bên dưới theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 vét cạn	Cách 2 QHĐ $O(len^2)$	Cách 3 QHĐ trên hiệu	Cách 4 cây phân đoạn
Subtask 1 (25%)	$n \le 20$, $Q = 1$	1–5	5/5	5/5	5/5	5/5
Subtask 2 (25%)	$n, Q \le 200$	6–10	1/5	5/5	5/5	5/5
Subtask 3 (25%)	$n, Q \le 3000$	11–15	0/5	0/5	5/5	5/5
Subtask 4 (25%)	$n, Q \le 2 \cdot 10^5$	16–20	0/5	0/5	0/5	5/5

Cách 1Subtask 1: vét cạn mọi cách cắt

Đoạn $[l, r]$ có $len = r - l + 1$ phần tử, giữa hai phần tử kề nhau có $len - 1$ chỗ, mỗi chỗ cắt hoặc không cắt → $2^{len - 1}$ cách chia. Dùng bitmask: bit $k - 1$ bằng 1 nghĩa là cắt giữa $a_{l+k-1}$ và $a_{l+k}$. Duyệt từ trái sang, giữ max/min của đoạn đang mở; gặp chỗ cắt thì cộng mx - mn vào tổng và mở đoạn mới.

C++▶ Chạy tay từng dòng codeCách 1: thử mọi cách cắt bằng bitmask.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(Q \cdot 2^{n} \cdot n)$

Kết quả chạy thật: bản C++ đúng 6/20 test, sai test 20, quá thời gian test 7–19, test đúng chạy lâu nhất 0,039 giây. Bản Python đúng 3/20 test, quá thời gian test 2–4, 7–20, test đúng chạy lâu nhất 0,151 giây. Bản C++ ăn subtask 1 (25%) – với $n = 20$ chỉ có $2^{19} \approx 5 \cdot 10^5$ cách chia; các test sau đó $len$ lớn nên vô vọng.

Cách 2Subtask 2: quy hoạch động O(len²) mỗi truy vấn

Gọi $f[i]$ là tổng giá trị lớn nhất khi chia đoạn $a_l..a_i$. Đoạn con cuối cùng là $a_j..a_i$ với $l \le j \le i$, nên:

$$f[i] = \max_{l \le j \le i}\Big(f[j - 1] + \max(a_j..a_i) - \min(a_j..a_i)\Big), \qquad f[l - 1] = 0.$$

Cho $j$ chạy lùi từ $i$ về $l$ thì max/min của $a_j..a_i$ cập nhật được trong $O(1)$. Thao tác loại 1 cứ cộng trực tiếp $O(n)$.

C++▶ Chạy tay từng dòng codeCách 2: f[i] = max(f[j − 1] + max − min của đoạn cuối a[j..i]).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(Q \cdot n^2)$

Kết quả chạy thật: bản C++ đúng 10/20 test, quá thời gian test 11–20, test đúng chạy lâu nhất 0,005 giây. Bản Python đúng 10/20 test, quá thời gian test 11–20, test đúng chạy lâu nhất 0,117 giây. Qua subtask 1, 2 (50%). Với $n = Q = 3000$, $Q \cdot n^2 / 2 \approx 1{,}35 \cdot 10^{10}$ phép tính – quá chậm.

Nhận xétĐưa về mảng hiệu

Gọi $d_i = a_{i+1} - a_i$ là hiệu kề nhau. Hai nhận xét then chốt:

Nhận xét 1 – đoạn đơn điệu

Nếu một đoạn con đơn điệu (không giảm hoặc không tăng) thì giá trị của nó (max − min) đúng bằng tổng $|d_i|$ của các hiệu bên trong đoạn. Mỗi chỗ cắt giữa $a_i$ và $a_{i+1}$ thì hiệu $d_i$ không được tính.

Nhận xét 2 – bài toán chọn hiệu

Đáp án của truy vấn $[l, r]$ = tổng $|d_i|$ lớn nhất của một tập hiệu được chọn trong $d_l, \ldots, d_{r-1}$, sao cho hai hiệu kề nhau cùng được chọn thì không trái dấu.

Vì sao đúng?

• Chọn hiệu → cách chia: trước hết bỏ chọn mọi hiệu bằng 0 (tổng không đổi, tập vẫn hợp lệ). Sau đó cắt tại mọi hiệu không được chọn. Mỗi đoạn tạo thành gồm các hiệu được chọn liên tiếp, khác 0 và kề nhau không trái dấu, tức là cùng dấu – đoạn đơn điệu, giá trị đoạn = tổng $|d|$ của nó. Vậy mỗi tập hợp lệ cho một cách chia có tổng giá trị đúng bằng tổng đã chọn.
• Cách chia → chọn hiệu: xét một đoạn con bất kì, gọi $p$ là vị trí phần tử nhỏ nhất, $q$ là vị trí lớn nhất (giả sử $p < q$). Giá trị đoạn $= a_q - a_p = d_p + \cdots + d_{q-1} \le$ tổng các hiệu dương trong khoảng đó. Chọn các hiệu dương này (cùng dấu nên không xung đột; các hiệu ở chỗ cắt giữa hai đoạn không được chọn). Làm vậy cho mọi đoạn ta được một tập hợp lệ có tổng ≥ tổng giá trị cách chia.

Hai chiều cùng đúng nên hai đại lượng max bằng nhau. Một điểm rất lợi: thao tác 1 l r x cộng $x$ vào cả đoạn thì các hiệu bên trong đoạn không đổi, chỉ $d_{l-1}$ tăng $x$ và $d_r$ giảm $x$!

Em nhập dãy rồi bấm Tiếp để xem quy hoạch động chọn hiệu chạy từ trái sang phải (mũi tên xanh lên là hiệu dương, đỏ xuống là hiệu âm), bước cuối truy vết ra cách chia tối ưu:

Dãy a:

Ví dụ nhanh:

Cách 3Subtask 3: QHĐ O(len) trên mảng hiệu

Duyệt các hiệu $d_l, \ldots, d_{r-1}$ từ trái sang, giữ 2 giá trị:

• g0 = tổng lớn nhất khi hiệu vừa xét không được chọn;
• g1 = tổng lớn nhất khi hiệu vừa xét được chọn.

Với hiệu mới $d_i$: không chọn thì n0 = max(g0, g1); chọn thì cộng $|d_i|$ vào g0, hoặc vào g1 nếu $d_{i-1}$ và $d_i$ không trái dấu.

C++▶ Chạy tay từng dòng codeCách 3: QHĐ hai trạng thái (hiệu trước có chọn hay không) trên mảng hiệu.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. g1 ban đầu là "âm vô cùng" (LLONG_MIN / 2 để cộng thêm không bị tràn) vì trước $d_l$ chưa có hiệu nào được chọn.
2. Thao tác loại 1 giờ chỉ là 2 phép gán $O(1)$; truy vấn loại 2 là $O(r - l)$.

Không gian$O(n)$

Thời gian$O(n + Q \cdot n)$

Kết quả chạy thật: bản C++ đúng 15/20 test, quá thời gian test 16–20, test đúng chạy lâu nhất 0,012 giây. Bản Python đúng 15/20 test, quá thời gian test 16–20, test đúng chạy lâu nhất 0,677 giây. Qua 3 subtask (75%); subtask 4 có tới $2 \cdot 10^5 \cdot 2 \cdot 10^5 / 2 = 2 \cdot 10^{10}$ bước nên quá thời gian.

Cách 4Cây phân đoạn, mỗi nút một ma trận 2×2

QHĐ ở cách 3 đi từ trái sang phải, nhưng thông tin cần để "nối" hai khúc liền nhau rất ít: khúc trái có chọn hiệu cuối của nó không, khúc phải có chọn hiệu đầu của nó không, và hai hiệu ở chỗ nối có trái dấu không. Vì vậy mỗi nút cây phân đoạn (quản lí các hiệu $d_{lo..hi}$) lưu:

• b[x][y] = tổng lớn nhất của một tập chọn hợp lệ trong $d_{lo..hi}$, với $x = 1$ nếu $d_{lo}$ được chọn, $y = 1$ nếu $d_{hi}$ được chọn (−∞ nếu không thể);
• lv, rv = giá trị $d_{lo}$ và $d_{hi}$.

Gộp hai nút L (trái) và R (phải)

$t.b[x][y]$ $= \max_{p, s \in \{0, 1\}} \big(L.b[x][p] + R.b[s][y]\big)$, bỏ trường hợp $p = s = 1$ khi L.rv và R.lv trái dấu.
Lá (một hiệu $v$): $b[0][0] = 0$, $b[1][1] = |v|$, $b[0][1]$ $= b[1][0]$ $= -\infty$.

Thao tác loại 1 = cập nhật 2 lá $d_{l-1}, d_r$ ($O(\log n)$); truy vấn loại 2 = gộp các nút phủ $[l, r-1]$ theo đúng thứ tự từ trái sang phải (phép gộp không giao hoán!) rồi lấy max 4 ô của kết quả.

C++▶ Chạy tay từng dòng codeCách 4: cây phân đoạn trên mảng hiệu, mỗi nút lưu ma trận b[2][2].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Phép gộp merge() và hàm leaf() được tính gộp trong một bước ở dòng gọi chúng cho gọn.

1. Hàm query duyệt cây theo thứ tự trái → phải nên các nút được gộp vào res đúng thứ tự; biến has báo res đã có dữ liệu chưa.
2. Khi gộp mình bỏ qua các ô −∞ thay vì cộng, nên không lo tràn số.
3. Trường hợp $l = r$ (một phần tử) đáp án là 0; $n = 1$ thì không có hiệu nào – mình tạo một lá giả để cây không rỗng.

Không gian$O(n)$

Thời gian$O((n + Q) \log n)$

Kết quả chạy thật: bản C++ đúng 20/20 test, test đúng chạy lâu nhất 0,429 giây. Mình không viết bản Python cho cách này: $2 \cdot 10^5$ thao tác × $\log n$ lần gộp ma trận trong Python chắc chắn không kịp 1 giây.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất (test đúng)	Điểm theo subtask
1. Vét cạn cách cắt	C++	6/20	0,039 s	25%
	Python	3/20	0,151 s	0%
2. QHĐ $O(len^2)$	C++	10/20	0,005 s	50%
	Python	10/20	0,117 s	50%
3. QHĐ trên mảng hiệu	C++	15/20	0,012 s	75%
	Python	15/20	0,677 s	75%
4. Cây phân đoạn	C++	20/20	0,429 s	100%

Ghi chú của mình: thời gian là thời gian CPU trên máy mình, giới hạn 1 giây. Mỗi cách ăn thêm đúng một subtask: vét cạn (25%) → QHĐ $O(len^2)$ (50%) → nhận xét mảng hiệu + QHĐ $O(len)$ (75%) → cây phân đoạn (100%, cũng là lời giải đã AC trên hệ thống chấm chính thức). Bài học: (1) với thao tác "cộng cả đoạn", hãy nghĩ tới mảng hiệu; (2) một QHĐ chạy trái → phải với ít trạng thái thường "gộp" được trên cây phân đoạn bằng cách lưu trạng thái ở hai đầu mỗi nút.

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 😇