Dãy số tổng k (Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng B, C2)

Nguồn: Tin học trẻ 2023 Độ khó: Khá Cây phân đoạn Tổng tiền tố Set

Đề bài

Nguồn đề: Hội thi Tin học trẻ toàn quốc 2023 – Vòng khu vực miền Bắc & miền Nam – Bảng B, C2 (bài Dãy số tổng k). Miền Bắc và miền Nam thi chung một đề, miền Trung có đề riêng. Đề bên dưới do mình viết lại bằng lời của mình cho dễ hiểu (giữ đúng nghĩa, đúng số liệu và ví dụ của đề gốc).

Cho dãy $a_1, a_2, \dots, a_n$, mỗi phần tử bằng $1$ hoặc $-1$. Có $q$ thao tác, mỗi thao tác thuộc một trong hai loại:

1. 1 i v ($1 \le i \le n$, $v \in \{-1, 1\}$): gán $a_i = v$;
2. 2 l r k ($1 \le l \le r \le n$, $|k| \le n$): tìm hai số nguyên $x, y$ với $l \le x \le y \le r$ và $a_x + a_{x+1} + \dots + a_y = k$.

Yêu cầu: thực hiện lần lượt các thao tác và trả lời các thao tác loại 2.

Dữ liệu vào:

• Dòng 1: hai số $n, q$ ($1 \le n, q \le 10^5$).
• Dòng 2: $n$ số $a_1, \dots, a_n$ ($a_i \in \{-1, 1\}$).
• $q$ dòng tiếp theo, mỗi dòng một thao tác theo dạng trên.

Kết quả: với mỗi thao tác loại 2 (theo thứ tự), in trên một dòng hai số $x, y$ bất kỳ thoả mãn; nếu không có thì in $-1$.

Subtask:

• Subtask 1 (20%): $k = 0$ với mọi thao tác loại 2;
• Subtask 2 (20%): $n, q \le 5000$;
• Subtask 3 (30%): không có thao tác loại 1;
• Subtask 4 (30%): không có ràng buộc gì thêm.

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

Ví dụ – input

5 8
1 -1 -1 1 1
2 1 4 0
2 1 4 -3
1 4 -1
2 1 5 -3
1 3 1
1 1 -1
1 5 -1
2 1 5 -3

Ví dụ – output

3 4
-1
2 4
1 5

Giải thích: câu 1: $a_3 + a_4 = -1 + 1 = 0$. Câu 2: trong $[1, 4]$ không có đoạn nào tổng $-3$. Sau khi gán $a_4 = -1$, dãy là $1, -1, -1, -1, 1$ và $a_2 + a_3 + a_4 = -3$. Sau ba lần gán tiếp theo, dãy là $-1, -1, 1, -1, -1$ và tổng cả dãy bằng $-3$.

Bài có nhiều đáp án: in cặp $(x, y)$ nào đúng cũng được (trên CLUE có checker riêng). Ví dụ lời giải của mình in 1 2 cho câu 1 thay vì 3 4.

Lời mở đầu

Dãy chỉ gồm $1$ và $-1$ là một dữ kiện "đắt giá": tổng của một đoạn khi thêm/bớt một phần tử chỉ thay đổi đúng 1 đơn vị. Nhờ tính chất đó, câu hỏi "có đoạn nào tổng bằng $k$?" quy về câu hỏi "đoạn con có tổng lớn nhất / nhỏ nhất là bao nhiêu?" – một bài kinh điển của cây phân đoạn. Mình đi từ cách $O(n)$ mỗi câu hỏi (40 điểm) tới cách $O(\log n)$ (full).

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:

Bộ test20 testÝ tưởngtính liên tụcCách 1O(n) – 20đCách 2+ set – 40đCách 3cây phân đoạnTổng kếtkết quả

Bộ testBộ test có gì?

Bộ test trên CLUE do mình tự sinh theo đúng giới hạn và tỉ lệ điểm subtask của đề: 20 test (test 1 là ví dụ, thuộc subtask 2). Các test lớn đều có $n = q = 10^5$, với nhiều kiểu dãy: ngẫu nhiên, lệch về một dấu (nhiều câu $-1$), các khúc dài cùng dấu, xen kẽ...

Subtask	Test	$n$	$q$	Số thao tác 1	Số thao tác 2	Số câu $k = 0$	Số câu trả lời $-1$	Kiểu dãy
Subtask 1	2	1	10	4	6	6	6	ngẫu nhiên nhỏ
	3	100.000	100.000	50.038	49.962	49.962	3.616	ngẫu nhiên
	4	100.000	100.000	30.118	69.882	69.882	18.062	gần như toàn 1
	5	100.000	100.000	39.953	60.047	60.047	8.867	các khúc dài cùng dấu
Subtask 2	1	5	8	4	4	1	1	ví dụ của đề
	6	5.000	5.000	1.984	3.016	77	1.927	ngẫu nhiên
	7	5.000	5.000	1.540	3.460	70	2.173	lệch về một dấu
	8	4.999	5.000	2.527	2.473	57	1.223	các khúc dài cùng dấu
Subtask 3	9	1	1	0	1	1	1	$n = 1$
	10	100.000	100.000	0	100.000	2.254	61.610	ngẫu nhiên
	11	100.000	100.000	0	100.000	2.199	59.716	lệch về một dấu
	12	100.000	100.000	0	100.000	2.189	46.842	các khúc dài cùng dấu
	13	100.000	100.000	0	100.000	2.181	57.669	gần như toàn 1
	14	100.000	100.000	0	100.000	2.212	90.697	xen kẽ $1, -1$
Subtask 4	15	100.000	100.000	50.200	49.800	1.140	31.268	ngẫu nhiên
	16	100.000	100.000	49.861	50.139	1.160	30.466	lệch về một dấu
	17	100.000	100.000	29.950	70.050	1.578	33.400	các khúc dài cùng dấu
	18	100.000	100.000	50.005	49.995	1.108	28.418	gần như toàn 1
	19	100.000	100.000	20.010	79.990	1.815	45.655	gần như toàn $-1$
	20	100.000	100.000	60.133	39.867	936	26.923	gần như xen kẽ

Đã nộp thử trên bộ chấm chính thức

Lời giải cuối cùng (cách 3) mình đã nộp lên hệ thống chấm chính thức của Hội thi (tinhoctre.vn) và được 100/100 điểm (AC).

Kết quả chạy thật các cách bên dưới (chấm bằng checker) theo từng subtask:

Subtask	Điều kiện	Test	Cách 1 C++	Cách 1 Python	Cách 2 C++	Cách 2 Python	Cách 3 C++
Subtask 1 (20%)	$k = 0$ với mọi thao tác loại 2	2–5	2/4	1/4	4/4	3/4	4/4
Subtask 2 (20%)	$n, q \le 5000$	1, 6–8	4/4	4/4	4/4	4/4	4/4
Subtask 3 (30%)	không có thao tác loại 1	9–14	1/6	1/6	1/6	1/6	6/6
Subtask 4 (30%)	không ràng buộc thêm	15–20	0/6	0/6	0/6	0/6	6/6

Ý tưởngCác tổng đạt được là một đoạn số liên tiếp

Nhận xét 1 (tính liên tục). Trong đoạn $[l, r]$, gọi $\text{maxSub}$ và $\text{minSub}$ là tổng lớn nhất và nhỏ nhất của một đoạn con khác rỗng. Mọi số nguyên $k$ trong $[\text{minSub}, \text{maxSub}]$ đều là tổng của một đoạn con nào đó. Thật vậy, lấy đoạn con $[x, y]$ có tổng lớn nhất (khi $k \ge 1$): phần tử đầu $a_x$ phải bằng $1$ (nếu là $-1$ thì bỏ nó đi tổng lớn hơn). Xét các tổng $a_x$, $a_x + a_{x+1}$, ..., $a_x + \dots + a_y$: bắt đầu từ $1$, kết thúc ở $\text{maxSub}$, mỗi bước thay đổi đúng $\pm 1$ – nên đi qua mọi giá trị từ $1$ tới $\text{maxSub}$, trong đó có $k$. Vị trí $j$ đầu tiên có $a_x + \dots + a_j \ge k$ thì tổng đúng bằng $k$.

Vậy với $k > 0$: có đáp án $\iff k \le \text{maxSub}$, đáp án là $x$ = đầu đoạn tổng lớn nhất, $y$ = vị trí đầu tiên tổng từ $x$ đạt $k$. Với $k < 0$: làm y hệt trên dãy đảo dấu $-a$ với $|k|$.

Nhận xét 2 ($k = 0$). Đoạn có tổng 0 thì có số $1$ và số $-1$, nên có hai phần tử kề nhau khác nhau – và chính hai phần tử đó đã có tổng 0. Vậy chỉ cần tìm một vị trí $i \in [l, r - 1]$ có $a_i \ne a_{i+1}$.

Em nhập dãy và câu hỏi rồi bấm Tiếp để xem cách tìm đoạn tổng lớn nhất (thuật toán Kadane) rồi đi từ $x$ tới khi tổng đạt $k$:

Dãy a = l = r = k =

Ví dụ nhanh:

Cách 1Tổng tiền tố + đánh dấu, O(n) mỗi câu hỏi (Subtask 2)

Chưa cần nhận xét nào: với tiền tố $P_j = a_1 + \dots + a_j$, cần $l - 1 \le x - 1 < y \le r$ với $P_y - P_{x-1} = k$. Duyệt $j$ từ $l - 1$ tới $r$; mỗi giá trị tiền tố ghi lại chỉ số đầu tiên nó xuất hiện trong dau[P + n] (cộng $n$ vì $P$ có thể âm). Tới $j \ge l$, nếu giá trị $P_j - k$ đã xuất hiện thì có đáp án. Mảng lan ghi "giá trị này được ghi ở câu hỏi số mấy" để khỏi phải xoá mảng dau sau mỗi câu. Gán $a_i$ thì tính lại các tiền tố từ $i$.

C++▶ Chạy tay từng dòng codeCách 1: duyệt tiền tố trong [l − 1, r], ghi lần xuất hiện đầu tiên của mỗi giá trị, O(n) mỗi câu.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(n)$ mỗi thao tác, tổng $O(n \cdot q)$

Kết quả chạy thật (chấm bằng checker): Bản C++ đúng 7/20 test, quá thời gian test 3, 5, 10–20 (các test đúng chạy lâu nhất 0.914s) → 20 điểm (subtask 2). Bản Python đúng 6/20 test, quá thời gian test 3–5, 10–20 (các test đúng chạy lâu nhất 0.862s). Các test có $n = q = 10^5$ cần tới $10^{10}$ phép tính nên quá thời gian.

Cách 2Tập vị trí kề khác dấu cho k = 0 (Subtask 1, 2)

Dùng nhận xét 2: giữ set<int> khac gồm các $i$ có $a_i \ne a_{i+1}$. Câu hỏi $k = 0$: khac.lower_bound(l) cho vị trí $i \ge l$ nhỏ nhất, có đáp án nếu $i + 1 \le r$. Gán $a_i$ chỉ ảnh hưởng hai cặp $(i - 1, i)$ và $(i, i + 1)$. Câu hỏi $k \ne 0$ vẫn làm như cách 1, nhưng tiền tố chỉ được tính lại khi thật sự cần (lười tính) – nhờ vậy subtask 1 (toàn $k = 0$) không bao giờ phải tính lại tiền tố.

C++▶ Chạy tay từng dòng codeCách 2: k = 0 trả lời bằng set các vị trí kề khác dấu; k ≠ 0 như cách 1, tiền tố chỉ tính lại khi cần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n)$

Thời gian$O(\log n)$ cho gán và $k = 0$, $O(n)$ cho $k \ne 0$

Kết quả chạy thật: Bản C++ đúng 9/20 test, quá thời gian test 10–20 (các test đúng chạy lâu nhất 0.106s) → 40 điểm (subtask 1, 2). Bản Python đúng 8/20 test, quá thời gian test 3, 10–20 (các test đúng chạy lâu nhất 0.789s) – bản Python không có set có thứ tự nên dùng danh sách đã sắp xếp + bisect; chèn/xoá phần tử giữa danh sách tốn $O(n)$ nên test 3 (nhiều lần gán) bị chậm.

Cách 3Cây phân đoạn: đoạn con tổng lớn nhất (full)

Dùng nhận xét 1. Mỗi nút cây phân đoạn quản lý đoạn $[l, r]$ lưu:

• sum: tổng cả đoạn;
• pre, preEnd: tiền tố (khác rỗng) có tổng lớn nhất và vị trí kết thúc;
• suf, sufBeg: hậu tố có tổng lớn nhất và vị trí bắt đầu;
• best, bl, br: đoạn con có tổng lớn nhất và hai đầu của nó.

Gộp hai con $A$ (trái), $B$ (phải): pre là $A.pre$ hoặc $A.sum + B.pre$; suf là $B.suf$ hoặc $B.sum + A.suf$; best là lớn nhất của $A.best$, $B.best$ và $A.suf + B.pre$ (đoạn vắt qua giữa). Giữ hai cây: pos cho dãy $a$, neg cho dãy $-a$, và set diff cho $k = 0$.

Với câu hỏi $k \ne 0$: query gộp các nút phủ $[l, r]$ để có đoạn tổng lớn nhất $[bl, br]$. Nếu best >= |k| thì $x = bl$ và findFirst tìm $y$ nhỏ nhất $\ge x$ có $\text{sum}(x..y) \ge |k|$: đi qua các nút nằm bên phải $x$ theo thứ tự trái → phải, nút nào có acc + pre < k thì bỏ qua cả nút (cộng sum vào acc), gặp nút đầu tiên có acc + pre >= k thì đi xuống: con trái đủ thì vào trái, không thì cộng tổng con trái rồi vào phải. Vì tổng tăng từng 1 nên $y$ tìm được có tổng đúng bằng $|k|$, và $y \le br \le r$.

C++▶ Chạy tay từng dòng codeCách 3: hai cây phân đoạn (a và −a) lưu đoạn con tổng lớn nhất; findFirst đi xuống cây tìm y.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Các hàm build, update, query của cây được gộp thành một bước (hình cây cho thấy kết quả); hàm findFirst được chạy từng bước đi xuống.

Không gian$O(n)$

Thời gian$O(\log n)$ mỗi thao tác

Kết quả chạy thật: Bản C++ đúng 20/20 test, chạy lâu nhất 0.282s. Full điểm. Mình không viết bản Python cho cách này: cây phân đoạn với $2 \times 10^5$ thao tác trên hai cây bằng Python sẽ vượt xa 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. Tiền tố + đánh dấu, O(n) mỗi câu hỏi	C++	7/20	0.914s	20%
	Python	6/20	0.862s	20%
2. Thêm tập vị trí kề khác dấu cho k = 0	C++	9/20	0.106s	40%
	Python	8/20	0.789s	20%
3. Cây phân đoạn: đoạn con tổng max + đi xuống cây	C++	20/20	0.282s	100%

Ghi chú của mình: bài nhiều đáp án nên kết quả ở đây được chấm bằng checker của mình (giống trên CLUE); thời gian là thời gian CPU trên máy mình (giới hạn 1 giây, test quá giờ bị dừng ở khoảng 4 giây). Bài học: khi dãy chỉ gồm $\pm 1$ (hoặc các bước thay đổi nhỏ), tập các giá trị đạt được thường là một đoạn liên tiếp – chỉ cần biết hai đầu mút (max, min) là trả lời được câu hỏi "có đạt được $k$ khô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 😇