Editorial for Truy vấn

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: Ta đơn giản duyệt qua từng giá trị $p$ ~p~ trong đoạn $[l,r]$ ~[l,r]~ và tìm kết quả.

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

Subtask 2: Gọi $right_i$ ~right_i~ ( $1 \le i \le N$ ~1 \le i \le N~) là chỉ số $j$ ~j~ nhỏ nhất thỏa mãn $j > i$ ~j > i~ và $A_j \neq A_i$ ~A_j \neq A_i~. Xây dựng $right_i$ ~right_i~ trong $O(N^2)$ ~O(N^2)~. Với mỗi truy vấn trên đoạn $[l,r]$ ~[l,r]~, ta chỉ cần kiểm tra hai giá trị $A_l$ ~A_l~ và $A_{right_l}$ ~A_{right_l}~:

Nếu $A_l \neq x$ ~A_l \neq x~ thì chỉ số $l$ ~l~ là kết quả cần tìm.
Ngược lại, nếu $right_l \le r$ ~right_l \le r~ và $A_{right_l} \neq x$ ~A_{right_l} \neq x~ thì $right_l$ ~right_l~ là kết quả cần tìm.
Nếu cả hai chỉ số $l$ ~l~ và $right_l$ ~right_l~ không thỏa mãn thì không có đáp án cho truy vấn.

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

Subtask 3: Ta có thể xây dựng $right_i$ ~right_i~ ( $1 \le i \le N$ ~1 \le i \le N~) với độ phức tạp $O(N)$ ~O(N)~ như sau:

Gọi $start$ ~start~ là chỉ số $i$ ~i~ nhỏ nhất cần tính $right_i$ ~right_i~. Ban đầu $start=1$ ~start=1~.
Duyệt qua các chỉ số $i$ ~i~ từ $2$ ~2~ đến $N$ ~N~.
Với mỗi chỉ số $i$ ~i~, kiểm tra $A_i \neq A_{i-1}$ ~A_i \neq A_{i-1}~. Nếu thỏa mãn, gán các giá trị $right_j=i$ ~right_j=i~ với $start \le j \le i-1$ ~start \le j \le i-1~ và cập nhật $start=i$ ~start=i~.

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

Editorial for Truy vấn

Comments