Trước khi vào bài viết này, tác giả xin cảm ơn:
đã góp ý cho bài viết này.
Đây là một bài màu vàng trong chuỗi bài AtCoder Grand Contest, nói qua một chút thì bài này cũng nằm trong chuỗi bài được khuyến nghị làm trong serie “More on Prefix Sums” của USACO Guide (bản thân nhận xét đây là một bài tricky nếu như ta không nắm chắc các kiến thức “cơ bản” của Lý thuyết đồ thị)
Link đề bài: https://atcoder.jp/contests/agc015/tasks/agc015_c
Chuỗi bài “More on Prefix Sums”: https://usaco.guide/silver/more-prefix-sums
Cho một lưới hình chữ nhật có N hàng và M cột hình vuông. Các hàng được đánh số từ 1 đến N theo thứ tự từ trên xuống, các cột được đánh số từ 1 đến M theo thứ tự từ trái sang phải. Mỗi ô vuông trong lưới được kí hiệu là $S_{i, j}$, nếu $S_{i, j} = 1$ thì ô đó được tô màu xanh dương, ngược lại nếu $S_{i, j} = 0$ thì ô đó được tô màu trắng. Với mỗi cặp ô xanh dương riêng biệt bất kì $a$ và $b$, chỉ có nhiều nhất một đường đi từ $a$, di chuyển đến các ô liền kề (chung cạnh), và cuối cùng đến $b$ mà không đi qua một ô vuông nhiều hơn 1 lần.
Đề bài đưa cho Q truy vấn, mỗi truy vấn chứa 2 tọa độ, tọa độ đầu tiên là của góc trái trên và tọa độ thứ hai là của góc phải dưới của một hình chữ nhật, hỏi có bao nhiêu thành phần liên thông của ô màu xanh dương ở trong hình chữ nhật đó?
Tự đọc trong link đề bài
Hình chữ nhật dưới đang thể hiện truy vấn thứ 2 (1 1 3 1), như ta thấy, chỉ có 2 thành phần liên thông mà thôi.
Giải thích thêm truy vấn 1, 2 tọa độ (1, 1) và (3, 4) đang thể hiện truy vấn hỏi toàn bộ lưới có bao nhiêu thành phần liên thông, đáp án là 3, cách giải thích như hình dưới đây.