Đăng nhập để tham gia lộ trình luyện tập

Queue trong lập trình thi đấu

1. Queue là gì?

Queue là cấu trúc dữ liệu hàng đợi hoạt động theo nguyên tắc:

$$\text{FIFO} = \text{First In, First Out}$$

Nghĩa là:

Phần tử được đưa vào trước sẽ được lấy ra trước.

Ví dụ, lần lượt đưa vào:

$$3,\ 7,\ 2,\ 5$$

thì thứ tự lấy ra là:

$$3,\ 7,\ 2,\ 5$$

Queue thường hỗ trợ các thao tác:

• push: thêm phần tử vào cuối hàng đợi.
• pop: xóa phần tử ở đầu hàng đợi.
• front: lấy phần tử đầu hàng đợi.
• back: lấy phần tử cuối hàng đợi.
• empty: kiểm tra hàng đợi có rỗng hay không.
• size: số phần tử hiện có.

Với cách cài đặt thích hợp, các thao tác cơ bản có độ phức tạp:

$$O(1)$$

---

2. Bản chất cần nhớ

Queue phù hợp khi bài toán có tính chất:

Trạng thái nào được sinh ra trước thì cần được xử lý trước.

Có thể hình dung:

$$\text{đưa trạng thái mới vào cuối} \rightarrow \text{xử lý trạng thái cũ ở đầu}$$

Đây là lý do Queue xuất hiện tự nhiên trong:

• Mô phỏng.
• BFS.
• Đường đi ngắn trên đồ thị không trọng số.
• Duyệt theo từng lớp.
• Multi-source BFS.
• Topological Sort bằng Kahn.
• Flood Fill.
• State-space BFS.
• Monotonic Queue.
• Sliding Window.
• 0-1 BFS.
• Một số tối ưu Quy hoạch động.

---

3. Queue cơ bản

Giả sử hàng đợi hiện tại là:

$$Q=[4,7,2]$$

Phần tử đầu:

$$\operatorname{front}(Q)=4$$

Phần tử cuối:

$$\operatorname{back}(Q)=2$$

Nếu thêm $9$:

$$Q=[4,7,2,9]$$

Nếu lấy một phần tử ra:

$$Q=[7,2,9]$$

Phần tử $4$ bị loại vì nằm ở đầu hàng đợi.

---

4. Queue trong bài toán mô phỏng

Dạng đơn giản nhất là mô phỏng một hàng người, hàng công việc hoặc danh sách sự kiện.

Dấu hiệu nhận biết:

• Người đến trước được phục vụ trước.
• Công việc được xử lý theo thứ tự xuất hiện.
• Mỗi bước lấy phần tử đầu rồi sinh thêm phần tử mới.
• Một phần tử xử lý xong có thể quay lại cuối hàng.

Mô hình tổng quát:

$$\text{front} \rightarrow \text{xử lý} \rightarrow \text{pop} \rightarrow \text{push trạng thái mới}$$

Các dạng thường gặp:

• Hàng người chờ.
• Máy in.
• Bộ lập lịch Round Robin.
• Trò chơi chuyền lượt.
• Hot Potato.
• Josephus biến thể.
• Mô phỏng tiến trình.

---

5. Circular Queue

Nếu tự cài Queue bằng mảng cố định, không nên liên tục dịch toàn bộ phần tử sau mỗi lần pop.

Ta sử dụng hai chỉ số:

$$head,\ tail$$

và xem mảng như một vòng tròn.

Chỉ số tiếp theo:

$$next(i)=(i+1)\bmod N$$

Khi đó:

• Thêm cuối: cập nhật $tail$.
• Xóa đầu: cập nhật $head$.

Mỗi thao tác vẫn là:

$$O(1)$$

Circular Queue đặc biệt hữu ích khi:

• Bộ nhớ có kích thước cố định.
• Dữ liệu được xử lý liên tục.
• Cần tự cài Queue không dùng thư viện.

---

6. BFS và Queue

Ứng dụng quan trọng nhất của Queue là Breadth-First Search.

BFS duyệt đồ thị theo từng lớp khoảng cách.

Nếu bắt đầu tại đỉnh $s$:

$$dist[s]=0$$

Nếu từ $u$ đi được sang $v$ bằng một cạnh:

$$dist[v]=dist[u]+1$$

với điều kiện $v$ chưa được thăm.

Queue đảm bảo các đỉnh có khoảng cách nhỏ hơn được xử lý trước.

Thứ tự tổng quát:

• Đưa đỉnh xuất phát vào Queue.
• Lấy đỉnh đầu Queue.
• Xét tất cả đỉnh kề.
• Đỉnh chưa thăm được đánh dấu ngay.
• Gán khoảng cách.
• Đưa đỉnh mới vào cuối Queue.

---

7. Vì sao BFS tìm được đường đi ngắn nhất?

Trong đồ thị không trọng số, mỗi cạnh có thể xem như có chi phí:

$$w=1$$

BFS xử lý các đỉnh theo thứ tự:

$$0,1,2,3,\ldots$$

tính theo số cạnh từ nguồn.

Do đó lần đầu tiên đến được đỉnh $v$ chính là lúc tìm được khoảng cách nhỏ nhất:

$$dist[v]$$

BFS giải bài toán đường đi ngắn nhất khi:

$$w(e)=1$$

cho mọi cạnh $e$.

Độ phức tạp:

$$O(V+E)$$

với:

• $V$: số đỉnh.
• $E$: số cạnh.

---

8. Truy vết đường đi bằng BFS

Ngoài khoảng cách, lưu:

$$parent[v]=u$$

khi lần đầu đi từ $u$ sang $v$.

Muốn dựng đường từ $s$ đến $t$, đi ngược:

$$t \rightarrow parent[t] \rightarrow parent[parent[t]] \rightarrow \cdots \rightarrow s$$

sau đó đảo ngược thứ tự.

---

9. BFS trên lưới

Một ô $(x,y)$ được xem như một trạng thái.

Với lưới bốn hướng:

$$(-1,0),\ (1,0),\ (0,-1),\ (0,1)$$

Từ:

$$(x,y)$$

có thể sinh:

$$(x+dx_k,\ y+dy_k)$$

Điều kiện thường gồm:

• Không ra ngoài lưới.
• Không đi vào vật cản.
• Chưa được thăm.

Độ phức tạp với lưới $n\times m$:

$$O(nm)$$

---

10. Flood Fill bằng Queue

Flood Fill dùng BFS để tìm các ô thuộc cùng một thành phần liên thông.

Tư duy:

Chọn một ô chưa thăm, BFS từ ô đó sẽ đánh dấu toàn bộ vùng liên thông chứa nó.

Nếu cần đếm số vùng:

$$components \mathrel{+}=1$$

mỗi khi bắt đầu một BFS mới.

Ứng dụng:

• Đếm phòng.
• Đếm đảo.
• Đếm vùng màu.
• Đếm thành phần liên thông trên ma trận.

---

11. Multi-source BFS

Nếu có nhiều nguồn cùng bắt đầu tại thời điểm $0$, không cần chạy BFS nhiều lần.

Khởi tạo:

$$dist[s_i]=0$$

với mọi nguồn $s_i$.

Sau đó đưa tất cả nguồn vào Queue trước khi BFS.

Khi đó:

$$dist[v]=\min_i dist(s_i,v)$$

Nghĩa là khoảng cách từ $v$ đến nguồn gần nhất.

Độ phức tạp vẫn là:

$$O(V+E)$$

không phải:

$$O(K(V+E))$$

với $K$ là số nguồn.

Ứng dụng:

• Nhiều đám cháy lan đồng thời.
• Nhiều quái vật di chuyển.
• Khoảng cách tới cửa hàng gần nhất.
• Khoảng cách tới số $0$ gần nhất.
• Nhiều nguồn phát tín hiệu.
• Voronoi trên đồ thị không trọng số.

---

12. BFS theo từng lớp

Nếu cần xử lý riêng từng mức khoảng cách, tại mỗi vòng lấy:

$$sz=|Q|$$

Sau đó xử lý đúng $sz$ phần tử hiện tại.

Toàn bộ $sz$ phần tử này thuộc cùng một lớp.

Ứng dụng:

• Duyệt cây theo tầng.
• Tính số bước.
• Mô phỏng thời gian.
• Lan truyền theo từng phút.
• Level Order Traversal.

---

13. BFS trên không gian trạng thái

Đỉnh của BFS không nhất thiết là một số nguyên.

Một trạng thái có thể là:

$$(x,y)$$

hoặc:

$$(x,y,mask)$$

hoặc:

$$(u,k)$$

hoặc:

$$(position,status)$$

Điều quan trọng nhất là xác định:

$$\text{State}$$

và:

$$\text{Transition}$$

Nếu mỗi phép chuyển có cùng chi phí $1$, có thể dùng BFS.

Ví dụ:

$$state=(x,y,keyMask)$$

Khoảng cách phải lưu theo toàn bộ trạng thái:

$$dist[x][y][mask]$$

không thể chỉ lưu:

$$dist[x][y]$$

nếu trạng thái khóa ảnh hưởng tới tương lai.

---

14. Topological Sort bằng Queue

Thuật toán Kahn sử dụng Queue để sắp xếp topo DAG.

Gọi:

$$indeg[v]$$

là số cạnh đi vào đỉnh $v$.

Ban đầu đưa mọi đỉnh có:

$$indeg[v]=0$$

vào Queue.

Khi lấy $u$ ra, với mỗi cạnh:

$$u\rightarrow v$$

thực hiện:

$$indeg[v]\mathrel{-}=1$$

Nếu:

$$indeg[v]=0$$

thì đưa $v$ vào Queue.

Nếu số đỉnh lấy được nhỏ hơn $V$, đồ thị có chu trình.

Độ phức tạp:

$$O(V+E)$$

---

15. Deque

Deque là hàng đợi hai đầu.

Ta có thể:

• Thêm đầu.
• Thêm cuối.
• Xóa đầu.
• Xóa cuối.
• Xem phần tử đầu.
• Xem phần tử cuối.

Mỗi thao tác:

$$O(1)$$

Deque là nền tảng của:

• 0-1 BFS.
• Monotonic Queue.
• Sliding Window Minimum.
• Sliding Window Maximum.
• Một số tối ưu DP.

---

16. 0-1 BFS

Nếu trọng số cạnh chỉ thuộc:

$$w\in\{0,1\}$$

thì có thể dùng Deque thay vì Dijkstra.

Relax cạnh:

$$dist[v] > dist[u]+w$$

Nếu cập nhật được:

$$dist[v]=dist[u]+w$$

thì:

• Nếu $w=0$, đưa $v$ vào đầu Deque.
• Nếu $w=1$, đưa $v$ vào cuối Deque.

Tức là:

$$w=0 \Rightarrow push\_front$$ $$w=1 \Rightarrow push\_back$$

Bản chất:

Trạng thái không làm tăng khoảng cách phải được xử lý sớm hơn.

Độ phức tạp:

$$O(V+E)$$

---

17. Khi nào dùng BFS, 0-1 BFS hay Dijkstra?

Nếu mọi cạnh có:

$$w=1$$

dùng BFS.

Nếu:

$$w\in\{0,1\}$$

dùng 0-1 BFS.

Nếu:

$$w\ge 0$$

và trọng số tổng quát, thường dùng Dijkstra.

Phản xạ cần nhớ:

$$1 \rightarrow \text{BFS}$$ $$0/1 \rightarrow \text{0-1 BFS}$$ $$\text{trọng số không âm bất kỳ} \rightarrow \text{Dijkstra}$$

---

18. Queue có truy vấn Min hoặc Max

Queue thông thường không thể lấy giá trị nhỏ nhất trong:

$$O(1)$$

nếu không có cấu trúc bổ sung.

Ta có thể xây dựng Min Queue sao cho:

• push: $O(1)$ trung bình.
• pop: $O(1)$.
• minimum: $O(1)$.

Một phương pháp quan trọng là sử dụng Monotonic Queue.

---

19. Monotonic Queue

Monotonic Queue thường được cài bằng Deque.

Nó duy trì các phần tử theo thứ tự đơn điệu.

Có hai dạng chính:

• Monotonic Increasing Queue.
• Monotonic Decreasing Queue.

Mục tiêu:

Loại bỏ những phần tử chắc chắn không còn khả năng trở thành đáp án trong tương lai.

Đây là tư tưởng quan trọng nhất.

---

20. Monotonic Increasing Queue

Dùng để duy trì giá trị nhỏ nhất.

Ta giữ:

$$a[q_1]\le a[q_2]\le \cdots \le a[q_k]$$

Khi thêm phần tử mới $a[i]$, trong khi:

$$a[q_k]\ge a[i]$$

thì loại $q_k$ khỏi cuối.

Sau đó thêm $i$.

Khi đó phần tử nhỏ nhất luôn nằm ở đầu:

$$\min = a[q_1]$$

---

21. Monotonic Decreasing Queue

Dùng để duy trì giá trị lớn nhất.

Ta giữ:

$$a[q_1]\ge a[q_2]\ge \cdots \ge a[q_k]$$

Khi thêm $a[i]$, trong khi:

$$a[q_k]\le a[i]$$

thì loại phần tử cuối.

Sau đó thêm $i$.

Giá trị lớn nhất:

$$\max = a[q_1]$$

---

22. Vì sao được phép loại phần tử?

Giả sử đang tìm minimum.

Có hai phần tử:

$$j<i$$

nhưng:

$$a[j]\ge a[i]$$

Phần tử $i$:

• Xuất hiện muộn hơn.
• Không lớn hơn $j$.

Do đó trong mọi cửa sổ tương lai chứa cả hai, $j$ không thể tốt hơn $i$.

Vì vậy $j$ bị dominate bởi $i$ và có thể xóa vĩnh viễn.

Đây chính là bản chất của Monotonic Queue.

---

23. Sliding Window Minimum

Cho mảng:

$$a_1,a_2,\ldots,a_n$$

và cửa sổ kích thước $k$.

Cần tính:

$$\min(a_{i-k+1},\ldots,a_i)$$

cho mọi $i\ge k$.

Dùng Deque lưu chỉ số.

Khi xét $a[i]$:

• Loại đầu nếu chỉ số đã ra khỏi cửa sổ.
• Loại cuối trong khi giá trị cuối không tốt hơn $a[i]$.
• Thêm $i$ vào cuối.
• Đầu Deque là vị trí minimum.

Điều kiện phần tử hết hạn:

$$q_{front}<i-k+1$$

Độ phức tạp toàn bộ:

$$O(n)$$

---

24. Sliding Window Maximum

Tương tự Sliding Window Minimum nhưng duy trì Deque giảm dần.

Khi xét $a[i]$, loại cuối khi:

$$a[q_{back}]\le a[i]$$

Maximum hiện tại:

$$a[q_{front}]$$

Độ phức tạp:

$$O(n)$$

---

25. Vì sao Monotonic Queue là $O(n)$?

Một phần tử có thể:

• Được thêm vào Deque đúng một lần.
• Bị xóa khỏi Deque nhiều nhất một lần.

Do đó tổng số thao tác trên toàn bộ mảng là tuyến tính:

$$O(n)$$

Đây là amortized analysis.

Không phải mỗi vòng while chạy $O(n)$ độc lập.

---

26. Hai Monotonic Queue cùng lúc

Một dạng rất quan trọng là duy trì đồng thời:

$$\max(L,R)$$

và:

$$\min(L,R)$$

Ta dùng:

• Một Deque giảm dần cho maximum.
• Một Deque tăng dần cho minimum.

Khi đó có thể kiểm tra nhanh điều kiện:

$$\max(L,R)-\min(L,R)\le K$$

Ứng dụng:

• Longest Continuous Subarray.
• Đoạn dài nhất có độ dao động không quá $K$.
• Two Pointers kết hợp Monotonic Queue.

Độ phức tạp:

$$O(n)$$

---

27. Two Pointers kết hợp Monotonic Queue

Giữ cửa sổ:

$$[L,R]$$

Mỗi khi tăng $R$, thêm $a[R]$ vào hai Monotonic Queue.

Nếu điều kiện bị vi phạm:

$$\max(L,R)-\min(L,R)>K$$

thì tăng $L$ cho đến khi cửa sổ hợp lệ.

Mỗi chỉ số vào và ra cấu trúc số lần hữu hạn nên tổng độ phức tạp:

$$O(n)$$

---

28. Prefix Sum kết hợp Monotonic Queue

Một dạng nâng cao rất quan trọng xuất hiện trong bài toán tổng đoạn.

Đặt:

$$P_0=0$$ $$P_i=a_1+a_2+\cdots+a_i$$

Tổng đoạn:

$$sum(L,R)=P_R-P_{L-1}$$

Nhiều bài toán có thể biến thành tìm hai prefix:

$$P_j-P_i$$

thỏa mãn một điều kiện.

Nếu cần tìm ứng viên $P_i$ tốt nhất trong một miền trượt, Monotonic Queue có thể giảm:

$$O(n^2)$$

xuống:

$$O(n)$$

---

29. Shortest Subarray With Sum At Least K

Cần tìm đoạn ngắn nhất sao cho:

$$P_j-P_i\ge K$$

tương đương:

$$P_i\le P_j-K$$

Ta duy trì Deque các chỉ số prefix có giá trị tăng dần:

$$P[q_1]<P[q_2]<\cdots$$

Với mỗi $j$:

Nếu:

$$P_j-P[q_{front}]\ge K$$

thì có một đoạn hợp lệ.

Cập nhật:

$$ans=\min(ans,j-q_{front})$$

và tiếp tục loại đầu để thử tìm đoạn ngắn hơn.

Ở cuối, loại các prefix bị dominate:

$$P[q_{back}]\ge P_j$$

Đây là một trong những ứng dụng quan trọng nhất của Monotonic Queue.

---

30. Monotonic Queue trong Quy hoạch động

Một dạng tổng quát:

$$dp[i] = f(i) + \min_{j\in[i-k,i-1]} g(dp[j],j)$$

Nếu phần phụ thuộc vào $j$ có thể tách thành:

$$X_j$$

thì:

$$dp[i] = f(i) + \min_{j\in[i-k,i-1]}X_j$$

Ta chỉ cần duy trì minimum của $X_j$ trong một cửa sổ trượt.

Monotonic Queue biến mỗi transition từ:

$$O(k)$$

thành:

$$O(1)$$

amortized.

Tổng độ phức tạp giảm từ:

$$O(nk)$$

xuống:

$$O(n)$$

---

31. Mẫu DP cửa sổ trượt

Ví dụ:

$$dp[i] = a_i+\min_{i-k\le j<i}dp[j]$$

Thay vì duyệt:

$$j=i-k,\ldots,i-1$$

ta duy trì Deque chứa các chỉ số $j$ sao cho:

$$dp[q_1]\le dp[q_2]\le\cdots$$

Khi đó:

$$dp[i]=a_i+dp[q_{front}]$$

Độ phức tạp:

$$O(n)$$

---

32. DP với giới hạn khoảng cách

Một dạng phổ biến:

$$dp[i] = \max_{L_i\le j\le R_i} \{dp[j]+C_i\}$$

Nếu miền:

$$[L_i,R_i]$$

trượt dần sang phải, ta có thể duy trì các $dp[j]$ hợp lệ bằng Monotonic Queue.

Đây là dấu hiệu rất mạnh:

DP có transition lấy min/max trên một đoạn chỉ số liên tiếp đang trượt.

---

33. Bounded Knapsack và Monotonic Queue

Một dạng nâng cao là tối ưu Knapsack có giới hạn số lượng.

Giả sử một loại vật có:

• Trọng lượng $w$.
• Giá trị $v$.
• Số lượng tối đa $c$.

Transition:

$$newdp[x] = \max_{0\le k\le c} \{dp[x-kw]+kv\}$$

Xét các vị trí có cùng phần dư modulo $w$:

$$x=r+tw$$

Khi đó:

$$newdp[r+tw] = tv+ \max_{t-c\le j\le t} \{dp[r+jw]-jv\}$$

Đặt:

$$X_j=dp[r+jw]-jv$$

Ta cần maximum trên một cửa sổ:

$$[t-c,t]$$

Đây chính là Sliding Window Maximum.

Dùng Monotonic Queue có thể giảm một transition lớn xuống gần:

$$O(W)$$

cho mỗi loại vật, với $W$ là sức chứa ba lô.

Đây là một ứng dụng nâng cao rất quan trọng của Monotonic Queue trong DP.

---

34. Queue bằng hai Stack

Có thể xây dựng Queue bằng hai Stack:

$$S_{in},S_{out}$$

Khi thêm phần tử:

$$push\rightarrow S_{in}$$

Khi cần lấy đầu mà $S_{out}$ rỗng, chuyển toàn bộ:

$$S_{in}\rightarrow S_{out}$$

Thứ tự bị đảo nên phần tử cũ nhất nằm trên đỉnh $S_{out}$.

Độ phức tạp amortized mỗi thao tác:

$$O(1)$$

---

35. Min Queue bằng hai Min Stack

Nếu mỗi Stack có thể trả về minimum trong:

$$O(1)$$

thì Queue bằng hai Stack cũng có thể trả về minimum:

$$\min(Q) = \min(\min(S_{in}),\min(S_{out}))$$

Các thao tác vẫn có độ phức tạp amortized:

$$O(1)$$

Đây là một cách khác để xây dựng Queue hỗ trợ truy vấn min.

---

36. Bidirectional BFS

Nếu cần tìm đường từ $s$ đến $t$ trong không gian trạng thái rất lớn, có thể BFS từ hai phía.

Một phía bắt đầu tại:

$$s$$

phía kia tại:

$$t$$

Khi hai miền tìm kiếm gặp nhau, ghép kết quả.

Nếu hệ số phân nhánh là $b$ và khoảng cách là $d$, BFS thường cần khoảng:

$$O(b^d)$$

trạng thái.

Bidirectional BFS có thể giảm gần thành:

$$O(b^{d/2})$$

trên mỗi phía.

Hiệu quả đặc biệt khi:

• Có một nguồn và một đích rõ ràng.
• Phép chuyển có thể đi ngược.
• Không gian trạng thái lớn.

---

37. Queue và bài toán lan truyền

Nhiều bài mô tả quá trình lan truyền:

• Lửa.
• Nước.
• Virus.
• Sóng.
• Tin nhắn.
• Trạng thái.
• Khoảng cách.

Nếu mỗi bước lan sang các trạng thái kề trong đúng một đơn vị thời gian thì bản chất thường là:

$$\text{Multi-source BFS}$$

Thời điểm đến:

$$time[v]=time[u]+1$$

---

38. Queue và mô phỏng sự kiện

Không phải bài Queue nào cũng là BFS.

Nếu sự kiện phải xử lý đúng thứ tự xuất hiện, Queue thuần có thể đủ.

Nhưng nếu cần xử lý sự kiện có thời gian nhỏ nhất trước thì Queue thường không còn phù hợp.

Khi đó cần:

$$\text{Priority Queue}$$

Phân biệt:

$$\text{FIFO} \rightarrow \text{Queue}$$ $$\text{nhỏ nhất/lớn nhất trước} \rightarrow \text{Priority Queue}$$

---

39. Queue và Priority Queue khác nhau

Queue chọn phần tử theo:

$$\text{thứ tự được đưa vào}$$

Priority Queue chọn phần tử theo:

$$\text{độ ưu tiên}$$

Ví dụ:

BFS dùng Queue vì khoảng cách tăng theo từng lớp.

Dijkstra dùng Priority Queue vì cần luôn chọn đỉnh có:

$$dist[u]$$

nhỏ nhất hiện tại.

Không được nhầm hai cấu trúc này.

---

40. Queue và Deque khác nhau

Queue chỉ cho phép:

$$push\_back$$

và:

$$pop\_front$$

Deque cho phép cả:

$$push\_front,\ push\_back$$

và:

$$pop\_front,\ pop\_back$$

Do đó Deque mạnh hơn và là công cụ chính của:

• 0-1 BFS.
• Monotonic Queue.
• Sliding Window Minimum.
• Sliding Window Maximum.

---

41. Khi nào nghĩ đến Monotonic Queue?

Hãy nghĩ tới Monotonic Queue nếu bài có đồng thời các dấu hiệu:

• Cửa sổ trượt.
• Cần min hoặc max.
• Các ứng viên hết hạn theo thứ tự.
• Chỉ số chỉ di chuyển từ trái sang phải.
• Một ứng viên mới có thể làm ứng viên cũ trở nên vô dụng.
• DP cần min/max trên một đoạn chỉ số liên tiếp.

Mẫu đặc biệt quan trọng:

$$\min_{i-k\le j<i}X_j$$

hoặc:

$$\max_{i-k\le j<i}X_j$$

Nếu cửa sổ trượt theo $i$, cần nghĩ ngay tới Monotonic Queue.

---

42. Tư duy Dominance

Monotonic Queue hoạt động nhờ loại bỏ trạng thái bị dominate.

Nếu ứng viên $B$:

• Mới hơn $A$.
• Tốt hơn hoặc bằng $A$.

thì $A$ thường không còn cần thiết.

Ví dụ tìm minimum:

$$j<i$$

và:

$$a[j]\ge a[i]$$

thì $j$ bị dominate bởi $i$.

Phản xạ quan trọng:

Không chỉ hỏi phần tử nào tốt nhất hiện tại, mà phải hỏi phần tử nào còn khả năng trở thành tốt nhất trong tương lai.

---

43. Hai nguyên nhân xóa phần tử khỏi Monotonic Queue

Một phần tử bị xóa vì một trong hai lý do.

Hết hạn

Chỉ số không còn thuộc cửa sổ hiện tại.

Ví dụ:

$$q_{front}<i-k+1$$

Bị dominate

Một phần tử mới tốt hơn và tồn tại lâu hơn.

Ví dụ với minimum:

$$a[q_{back}]\ge a[i]$$

Phân biệt rõ hai nguyên nhân này là chìa khóa để viết đúng Monotonic Queue.

---

44. Vì sao nên lưu chỉ số thay vì chỉ lưu giá trị?

Trong Sliding Window, cần biết phần tử có hết hạn hay chưa.

Nếu chỉ lưu giá trị, ta không biết nó thuộc vị trí nào.

Do đó thông thường nên lưu:

$$index$$

Sau đó lấy giá trị qua:

$$a[index]$$

Điều này cho phép đồng thời kiểm tra:

• Giá trị.
• Vị trí.
• Hết hạn.
• Dominance.

---

45. Lỗi thường gặp với BFS

Các lỗi phổ biến:

• Đánh dấu visited quá muộn.
• Một đỉnh bị đưa vào Queue nhiều lần không cần thiết.
• Không kiểm tra biên trên lưới.
• Quên vật cản.
• Sai trạng thái.
• Dùng BFS cho cạnh có trọng số khác nhau.
• Không lưu đầy đủ state.
• Sai truy vết parent.

Quy tắc quan trọng:

Với BFS thông thường, nên đánh dấu trạng thái ngay khi đưa vào Queue.

---

46. Lỗi thường gặp với Monotonic Queue

Các lỗi phổ biến:

• Lưu giá trị thay vì chỉ số.
• Kiểm tra hết hạn sai.
• Nhầm dấu <, <=, >, >=.
• Xóa đầu và xóa cuối sai thứ tự.
• Duy trì tăng nhưng lại lấy maximum.
• Duy trì giảm nhưng lại lấy minimum.
• Không hiểu phần tử bằng nhau nên giữ phần tử nào.

Nếu muốn minimum và ưu tiên phần tử mới hơn, thường loại cuối khi:

$$a[q_{back}]\ge a[i]$$

Nếu muốn giữ phần tử cũ hơn khi bằng nhau, có thể dùng:

$$a[q_{back}]>a[i]$$

Việc chọn dấu phụ thuộc yêu cầu bài toán.

---

47. Công thức cốt lõi cần nhớ

BFS:

$$dist[v]=dist[u]+1$$

Multi-source BFS:

$$dist[v]=\min_{s\in S}dist(s,v)$$

0-1 BFS:

$$dist[v]=\min(dist[v],dist[u]+w)$$

với:

$$w\in\{0,1\}$$

Prefix Sum:

$$P_i=P_{i-1}+a_i$$

Tổng đoạn:

$$sum(L,R)=P_R-P_{L-1}$$

Sliding Window Minimum:

$$M_i=\min_{i-k+1\le j\le i}a_j$$

Sliding Window Maximum:

$$M_i=\max_{i-k+1\le j\le i}a_j$$

DP tối ưu bằng Monotonic Queue:

$$dp[i] = f(i) + \min_{i-k\le j<i}X_j$$

hoặc:

$$dp[i] = f(i) + \max_{i-k\le j<i}X_j$$

---

48. Bản đồ nhận dạng nhanh

Nếu đề nói:

Đi ít bước nhất trên đồ thị không trọng số

Nghĩ tới:

$$\text{BFS}$$

Nhiều nguồn xuất phát cùng lúc

Nghĩ tới:

$$\text{Multi-source BFS}$$

Cạnh chỉ có trọng số $0$ hoặc $1$

Nghĩ tới:

$$\text{0-1 BFS}$$

Xử lý đỉnh indegree bằng $0$

Nghĩ tới:

$$\text{Kahn + Queue}$$

Min hoặc max trong mọi cửa sổ độ dài $k$

Nghĩ tới:

$$\text{Monotonic Queue}$$

Đoạn dài nhất với $\max-\min\le K$

Nghĩ tới:

$$\text{Two Pointers + hai Monotonic Queue}$$

DP lấy min/max trên $k$ trạng thái gần nhất

Nghĩ tới:

$$\text{DP + Monotonic Queue}$$

Prefix Sum và cần tìm đoạn ngắn nhất thỏa tổng

Nghĩ tới:

$$\text{Prefix Sum + Monotonic Queue}$$

---

49. Cây tư duy chọn cấu trúc

Nếu cần xử lý theo đúng thứ tự xuất hiện:

$$\boxed{\text{Queue}}$$

Nếu cần thao tác cả hai đầu:

$$\boxed{\text{Deque}}$$

Nếu cần phần tử nhỏ nhất hoặc lớn nhất theo độ ưu tiên:

$$\boxed{\text{Priority Queue}}$$

Nếu cần min/max trên cửa sổ trượt:

$$\boxed{\text{Monotonic Queue}}$$

Nếu cần đường đi ngắn nhất với cạnh bằng $1$:

$$\boxed{\text{BFS}}$$

Nếu trọng số chỉ là $0$ và $1$:

$$\boxed{\text{0-1 BFS}}$$

---

50. Các mức cần thành thạo

Mức nền tảng:

• Queue FIFO.
• Push, pop, front.
• Circular Queue.
• Mô phỏng.

Mức đồ thị:

• BFS.
• Grid BFS.
• Flood Fill.
• Multi-source BFS.
• Truy vết BFS.
• State-space BFS.
• Level BFS.
• Kahn Topological Sort.

Mức Deque:

• Deque hai đầu.
• 0-1 BFS.
• Bidirectional BFS.

Mức Monotonic Queue:

• Sliding Window Minimum.
• Sliding Window Maximum.
• Hai Deque min/max.
• Two Pointers kết hợp Deque.
• Prefix Sum kết hợp Deque.
• Shortest Subarray.
• DP Sliding Window Optimization.
• Bounded Knapsack Optimization.

---

51. Phản xạ cốt lõi

Khi gặp Queue, không nên chỉ hỏi:

Có thể dùng queue hay không?

Cần hỏi theo thứ tự:

1. Trạng thái là gì?
2. Thứ tự xử lý trạng thái là gì?
3. Cạnh hoặc phép chuyển có chi phí bằng nhau không?
4. Có nhiều nguồn hay không?
5. Có cần thao tác cả hai đầu không?
6. Có cửa sổ trượt không?
7. Có truy vấn min/max không?
8. Có ứng viên nào bị dominate không?
9. Transition DP có phải min/max trên một đoạn trượt không?

Nếu trả lời đúng các câu hỏi này, phần lớn bài Queue trong lập trình thi đấu sẽ trở thành một trong các mẫu quen thuộc.

---

52. Kết luận

Queue không chỉ là cấu trúc dữ liệu FIFO cơ bản.

Trong lập trình thi đấu, hệ sinh thái Queue gồm:

$$\boxed{ \text{Queue} \rightarrow \text{BFS} \rightarrow \text{Multi-source BFS} \rightarrow \text{Deque} \rightarrow \text{0-1 BFS} \rightarrow \text{Monotonic Queue} \rightarrow \text{DP Optimization} }$$

Ba phản xạ quan trọng nhất cần hình thành là:

• FIFO $\rightarrow$ nghĩ đến Queue.
• Đường đi ngắn nhất với bước có cùng chi phí $\rightarrow$ nghĩ đến BFS.
• Min/Max trên một cửa sổ trượt $\rightarrow$ nghĩ đến Monotonic Queue.

Đặc biệt, Monotonic Queue cần được xem là một kỹ thuật độc lập trong lập trình thi đấu, không chỉ là một biến thể nhỏ của Queue, vì nó là cầu nối quan trọng giữa:

$$\text{Deque} + \text{Sliding Window} + \text{Prefix Sum} + \text{Two Pointers} + \text{Dynamic Programming}$$