Ta tạm gọi \(1\) số nguyên dương \(x\) là số đẹp nếu \(x\) or \(a = x\)
Gọi hàm \(F(l)\) là hàm tính số lượng số đẹp không vượt quá \(l\). Đáp án cho mỗi truy vấn sẽ là \(F(r) - F(l - 1)\).
Ta có thể xây dựng hàm này bằng cách sử dụng kỹ thuật tìm kiếm nhị phân, để tìm số đẹp nhỏ thứ \(k\), ta có thể chuyển \(k\) và \(a\) thành \(2\) dãy nhị phân.
Sau đó thực hiện chèn các bit \(1\) vào vị trí thứ \(i\) của số \(k\), nếu bit thứ \(i\) của \(a\) bằng \(1\). Gọi \(m\) là số \(k\) sau khi được chèn, khi đó \(m\) sẽ là số đẹp thứ \(k\).
Quay lại với việc tính hàm \(F(l)\), với \(l\) cố định, ta chỉ cần tìm số \(k\) lớn nhất sao cho số đẹp thứ \(k\) không vượt quá \(l\), khi đó đáp án cho hàm sẽ là \(k\).
Độ phức tạp cho thuật toán sẽ lả \(O(n.(logn) ^ 2)\)

NOTE:

• Ta có \(1\) thuật toán có thể giải trong \(O(n.logn)\), mình sẽ để lại xem như bài tập cho các bạn :333.