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 thực hiện lần lượt các truy vấn và tính kết quả.

Độ phức tạp: $O(QN)$ ~O(QN)~

Subtask 2: Với việc chỉ có truy vấn loại $2$ ~2~ $($ ~(~cập nhật đoạn $)$ ~)~ và truy vấn loại $3$ ~3~ $($ ~(~truy vấn đoạn $)$ ~)~, ta chỉ cần sử dụng cấu trúc Segment Tree kết hợp kỹ thuật Lan truyền lười nhác $($ ~(~Lazy Propagation $)$ ~)~ để xử lý.

Độ phức tạp: $O(Nlog(N)+Qlog(N))$ ~O(Nlog(N)+Qlog(N))~

Subtask 3: Ta có nhận xét rằng với mỗi giá trị $A_i$ ~A_i~, nếu không có truy vấn loại $2$ ~2~ thì việc thực hiện truy vấn loại $1$ ~1~ trên giá trị $A_i$ ~A_i~ này không vượt quá $\log(A_i)$ ~\log(A_i)~ lần. Khi đó, mỗi nút của cây phân đoạn sẽ được cập nhật không quá $\log(10^5) \approx 17$ ~\log(10^5) \approx 17~ lần.

Độ phức tạp: $O(Nlog(N)+Qlog(N)log(c))$ ~O(Nlog(N)+Qlog(N)log(c))~

Subtask 4: Ta có thể sử dụng kỹ thuật Lazy Propagation cho thao tác loại $1$ ~1~. Trong quá trình cập nhật tại nút $j$ ~j~ của cây, nếu toàn bộ phần tử tại nút $j$ ~j~ đều bằng $0$ ~0~ thì ta dừng việc cập nhật. Ngoài ra, nếu toàn bộ phần tử tại nút $j$ ~j~ đều mang cùng giá trị $a$ ~a~ thì ta tiến hành cập nhật giá trị $\lfloor \frac{a}{x} \rfloor$ ~\lfloor \frac{a}{x} \rfloor~ cho toàn bộ phần tử tại nút $j$ ~j~ và dừng việc cập nhật.

Độ phức tạp: $O(Nlog(N) + Qlog(N)log(c))$ ~O(Nlog(N) + Qlog(N)log(c))~

Editorial for Truy vấn

Comments