Nếu ta xem giá trị của mỗi loại phép thuật ~x~ là ~2^x~, và giá trị của mỗi phủ thuỷ là xor của tất cả các loại phép thuật, thì bài toán quy về: chia đoạn ~[l,r]~ thành nhiều đoạn nhất, sao cho xor của mỗi đoạn là ~2^m-1~. Gọi ~a_i~ là giá trị của phù thuỷ thứ ~i~.

Subtask 1: Mỗi vị trí ~i~ có 2 lựa chọn: hoặc ghép cùng nhóm với vị trí ~i-1~, hoặc bắt đầu một nhóm mới. Như vậy ta có thể duyệt toàn bộ ~2^n~ cách chia nhóm trong ~\mathcal{O}(2^n \cdot n)~ bằng duyệt bitmask hoặc ~\mathcal{O}(2^n)~ bằng đệ quy.

Subtask 2: Mỗi truy vấn cập nhật trong ~\mathcal{O}(1)~, trả lời trong ~\mathcal{O}(n)~.

• Quy hoạch động:

  • Gọi ~dp_i~ là số đoạn nhiều nhất có thể khi chia đoạn ~[l,i]~.

  • Công thức: ~dp_{l-1}=0~, ~dp_i \leftarrow dp_j+1~ nếu ~a_{j+1} \oplus \ldots \oplus a_i = 2^m-1~, hay ~pref_i \oplus pref_j = 2^m-1~ với ~pref_i~ là xor tiền tố từ ~l~ đến ~i~.

  • Để tính trong ~\mathcal{O}(n)~, ta lưu thêm một mảng ~best_x~ là ~dp_j~ tốt nhất với ~j<i~ và ~pref_j = x~. Khi đó với mỗi ~i~, ta cập nhật ~dp_i \leftarrow best_{(2^m-1) \oplus pref_i}~ và ~best_{pref_i} \leftarrow dp_i~.</p>

  • Tuy độ phức tạp là ~\mathcal{O}(q \cdot n)~ nhưng cách này constant khá lớn và có thể không AC.

• Tham lam:

  • Duyệt ~i~ từ ~l~ đến ~r~, nếu xor hiện tại là ~2^m-1~ ~\Rightarrow~ cắt thành một đoạn luôn.

  • Trường hợp còn thừa đoạn cuối không chia được: nếu giá trị của nó là ~0~ thì ghép với đoạn có giá trị ~2^m-1~ trước đó, ngược lại kết luận đáp án là ~-1~.

  • Độ phức tạp ~\mathcal{O}(q \cdot n)~ constant bé.

Subtask 3: Không có truy vấn cập nhật, nên ta có thể mô phỏng thuật tham bằng Binary Lifting.

• Gọi ~nxt_i~ là vị trí gần ~i~ nhất và ~a_i \oplus \ldots \oplus a_{nxt_i} = 2^m-1~.

• Khi đó với mỗi truy vấn ta chỉ cần gán liên tục ~l \rightarrow nxt_l+1 \rightarrow nxt_{nxt_l+1}+1 \ldots~, cho đến khi ~nxt_l>r~. Xét giá trị đoạn cuối: nếu nó là ~0~ hoặc ~2^m-1~ thì đáp án là số lần nhảy (~+1~ nếu như là ~2^m-1~), ngược lại là ~-1~.

• Tuy nhiên việc gán như vậy có thể mất ~\mathcal{O}(n)~ mỗi truy vấn, ta chuẩn bị trước mảng ~nxt_{ij}~ là kết quả khi nhảy ~2^j~ lần từ vị trí ~i~, và duyệt các bit ~j~ từ lớn về bé với mỗi truy vấn để lấy kết quả từ mảng ~nxt~. Độ phức tạp ~\mathcal{O}((n+q) \log n)~

Subtask 4: Mô phỏng thuật tham bằng Segment Tree. Cụ thể, với mỗi nút ~u~ biểu diễn đoạn ~[l,r]~ ta lưu:

• ~value~: xor của đoạn ~[l,r]~.

• ~cnt[u]~: số đoạn chia được nếu giá trị xor ban đầu là ~u~ (nghĩa là trước khi duyệt các phần tử trong đoạn ~[l,r]~ thì giá trị xor đã có sẵn ~u~).

• ~rem[u]~: phần dư của đoạn cuối nếu giá trị xor ban đầu là ~u~

Nút lá ~[i,i]~ có dạng:

• ~value=a_i~

• Nếu ~msk \oplus a_i = 2^m-1~ thì ~cnt[msk]=1~, ~rem[msk]=0~.

• Ngược lại ~cnt[msk] = 0~, ~rem[msk]=a[i]~.

Ghép 2 nút ~u,v~: Khi đã biết phần còn thừa của ~u~, ta có thể truy vấn vị trí tương ứng ở ~v~ để biết phần thừa khi ghép đoạn ~v~ sau đoạn ~u~, cụ thể:

• ~value = u.value \oplus v.value~

• ~cnt[msk] = u.cnt[msk] + v.cnt[u.rem[msk]]~

• ~rem[msk] = v.rem[u.rem[msk]]~

Từ đó bài toán quy về cập nhật điểm và truy vấn đoạn. Nếu xor đoạn ~[l,r]~ khác ~0~ và ~2^m-1~, hoặc ~cnt[0] = 0~, thì đáp án là ~-1~, ngược lại đáp án là ~cnt[0]~. Độ phức tạp: ~\mathcal{O}((n + q) \cdot 32 \cdot \log(n))~

Chứng minh thuật tham đúng

Đặt ~S=2^m-1~.

Giả sử chia được thành ~k~ nhóm hợp lệ, khi đó xor cả đoạn sẽ là ~0~ nếu ~k~ chẵn hoặc ~S~ nếu ~k~ lẻ. In ~-1~ nếu xor cả đoạn không thuộc 1 trong 2 trường hợp trên.

Dễ thấy cách tham trên sẽ luôn cho ra số nhóm lớn nhất. Giả sử cấu hình tìm được của cách tham là ~\{i_1, i_2, \ldots, i_k\}~, và cấu hình tốt hơn là ~\{i'_1, i'_2, \ldots, i'_{k'}\}~ với ~k' > k~. Khi đó sẽ có một điểm ~j~ có ~i'_j > i_j~, nhưng rõ ràng lùi ~i'_j~ về ~i_j~ thì sẽ có nhiều cơ hội tìm được thêm đoạn hơn ~\Rightarrow~ ~k = k'~.

Mặt khác, do xor cả đoạn chỉ là ~0~ hoặc ~S~, nên nếu thừa ra một đoạn không phải xor bằng ~S~, xor của nó chắc chắn là ~0~. Khi đó, nếu đã có 1 đoạn bằng ~S~ trước đó, ta chỉ cần ghép đoạn ~0~ này vào cùng đoạn ~S~ trước đó là được.