Editorial for Thành phần liên thông

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Yunan

Subtask 1: Với dãy hoán vị $P$ ~P~, ta tiến hành xây dựng các cạnh của đồ thị và đếm số thành phần liên thông.

Độ phức tạp: $O(Q.N^2)$ ~O(Q.N^2)~

Subtask 2: Ta xây dựng dãy hoán vị $Q$ ~Q~ là đảo ngược của dãy $P$ ~P~, cụ thể $Q_i=P_{N-i+1}$ ~Q_i=P_{N-i+1}~ $(1 \le i \le N)$ ~(1 \le i \le N)~. Khi đó, giữa hai đỉnh $u$ ~u~ và $v$ ~v~ có cạnh nối khi và chỉ khi $u<v$ ~u<v~ và $Q_u>Q_v$ ~Q_u>Q_v~.

Từ đó ta có nhận xét rằng với các chỉ số $j$ ~j~ thỏa mãn tất cả các số từ $1$ ~1~ đến $j$ ~j~ đều xuất hiện ở dãy tiền tố tại $j$ ~j~ sẽ tạo thành một thành phần liên thông. Hay nói cách khác, ta cần đếm các vị trí $j$ ~j~ thỏa mãn:

$\displaystyle \sum_{i=1}^{j} (Q_i-i) = 0$

Độ phức tạp: $O(Q.N)$ ~O(Q.N)~

Subtask 3: Ta có thể giải quyết bài toán bằng cách xây dựng mảng Tổng tiền tố $($ ~(~Prefix Sum $)$ ~)~ kết hợp cấu trúc Segment Tree để cập nhật và đếm số lượng chỉ số $j$ ~j~.

Độ phức tạp: $O((N+Q).\log(N))$ ~O((N+Q).\log(N))~

Editorial for Thành phần liên thông

Comments