Subtask 3

Nhận thấy rằng mỗi phép biến đổi có thể biểu diễn bằng một phép nhân ma trận. Xét phép biến ~s = s \oplus (s >> x)~. Nếu ~x \neq 0~ ta dựng một ma trận kích thước ~n \times n~. Với mỗi cột ~i~, ma trận sẽ có hàng ~i~ và hàng ~(i - x + n) \mod n~ bằng ~1~, các vị trí khác bằng ~0~. Nếu ~x = 0~, vì ~s \oplus s = 0~ nên ma trận chỉ toàn giá trị ~0~. Ta cũng coi số ở mỗi truy vấn là một số ~n~ bit, hay nói cách khác là ma trận ~1 \times n~.

Từ đó, gọi ~f_i~ là ma trận biểu diễn phép biến đổi tại vị trí ~i~. Với mỗi truy vấn, ta cần lấy ma trận ~1 \times n~ nhân với tất cả các ma trận từ ~l~ đến ~r~. Để đẩy nhanh tốc độ, ta sử dụng kĩ thuật ~\bf{sparse table}~, chuẩn bị trước giá trị ~g_{i, j}~ là tích các ma trận ~f_i, f_{i+1}, ..., f_{i + 2^j - 1}~. Để tối ưu bước nhân hai ma trận, ta biểu diễn ma trận hàng và ma trận cột của ~g_{i, j}~ và dùng phép ~\text{AND}~ cũng như hàm ~\text{__builtin_popcount}~. Độ phức tạp của việc nhân hai ma trận bây giờ là ~O(n^2)~.

Với mỗi truy vấn, ta thực hiện tối đa ~log2(m)~ bước nhảy, mỗi bước nhảy có độ dài là lũy thừa của ~2~. Ta không nhân các ma trận ~n \times n~ với nhau (như bước chuẩn bị) mà thực hiện lần lượt phép nhân của ma trận ~1 \times n~ với ma trận ~n \times n~. Độ phức tạp của việc nhân ma trận bây giờ chỉ còn ~O(n)~.

ĐPT: ~O(m \times \log2(m) \times n^2 + q \times \log2(m) \times n)~.

Subtask 4

Để cải tiến tốc độ của các truy vấn, ta sử dụng thuật toán chia để trị thay vì ~\bf{sparse table}~.

Thuật toán chia để trị như sau, xuất phát từ cặp ~x = 1, y = m~, lấy ~mid = (x + y) / 2~, ta hai mảng ~pref~ và ~suff~.

• ~pref[i]~ = ~f[i] \times f[i+1] \times ... \times f[mid]~ với ~x \leq i \leq mid~.
• ~suff[i]~ = ~f[mid+1] \times f[mid+2] \times ... \times f[i]~ với ~mid+1 \leq i \leq y~.

Dùng hai mảng ~pref~ và ~suff~ đã chuẩn bị ở trên, ta có thể tính đáp án cho các truy vấn ~l, r~ có ~x \leq l \leq mid < r \leq y~ bằng tối đa hai phép nhân ma trận kích thước ~1 \times n~ với ~n \times n~ thay vì ~log2(m)~ lần như ở ~\bf{Subtask 3}~. Sau đó tiếp tục gọi đệ quy tính toán với ~x_1 = x, y_1 = mid~ và ~x_2 = mid+1, y_2 = y~.

ĐPT: ~O(m \times \log2(m) \times n^2 + q \times n)~.