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)
Đề bài
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 i v($1 \le i \le n$, $v \in \{-1, 1\}$): gán $a_i = v$;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.
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 -33 4
-1
2 4
1 5Giả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à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 OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
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ẽ |
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$:
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$.
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ố.
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$.
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% |