Ta sử dụng kỹ thuật Chia căn để giải quyết bài toán.

Ta chia mảng thành các block gồm $S$ phần tử, dễ thấy có $\frac{N}{S}$ block. Xem các đoạn $[l, r]$ trong truy vấn là bao phủ các block hoàn chỉnh. Gọi $b_l$ là block chứa vị trí $l$.

Ta sử dụng hai mảng $set, add$ để cập nhật lười (lazy propagation) trên các block. Ban đầu ~add[i] = 0, set[i] = -1~.

• Khi có truy vấn ADD, ta sử dụng lazy để thêm vào, hay nói cách khác, tăng ~add[b_i]~ lên ~1~ ~(b_l \leq i \leq b_r)~.

• Khi có truy vấn SET, ta vẫn sử dụng lazy, tuy nhiên lúc này ta loại bỏ hoàn toàn các thông tin hiện có trong block ~i~ (đặt ~add[i] = 0, set[i] = x~).

• Khi có truy vấn COUNT, nếu $add[i] > 0$ thì đặt ~k = k - add[i]~, sau đó nếu ~set[i] = -1~ thì ta có thể đếm trong ~O(log)~ bằng fenwick tree. Ngược lại ta chỉ cần kiểm tra xem ~set[i] \geq k~ hay không.

Tuy nhiên nếu đoạn ~[l, r]~ không bao phủ các block hoàn chỉnh thì lúc này, ta sẽ rebuild lại ~b_l~ và ~b_r~ bằng những thông tin sẵn có trong hai mảng ~add~ và ~set~ sau đó duyệt trâu để đếm.

Độ phức tạp: ~O(Q*S.log + Q * \frac{N}{S} * log).~ Tuy nhiên ta thấy trong truy vấn COUNT vẫn tồn tại trường hợp đếm trong $O(1)$, do đó có thể đặt ~S \approx 600~.