Subtask 1

Khởi tạo ~q + 1~ mảng và thực hiện theo đúng yêu cầu ở mỗi truy vấn.

Độ phức tạp : ~O(n . q)~.

Subtask 2

Nhận thấy các mảng trên sẽ tạo thành một cây. Và mỗi mảng sẽ được xem là một đỉnh của cây.

Gọi ~ok_i~ có ý nghĩa kiểm tra xem giá trị ~i~ có tồn tại trong mảng ~0~ hay không ?

Gọi ~g_u~ là giá trị xor tất cả giá trị ~v_p~ với ~p~ là đỉnh nằm trên đường đi đơn từ đỉnh ~0~ đến đỉnh ~u~.

Từ mảng ~ok~ và ~g~ ta sẽ tìm được phần tử nhỏ nhất ở mỗi mảng.

Độ phức tạp : ~O(q.max(A_{0_i}))~.

Subtask 3

Gọi ~g_u~ là giá trị xor tất cả giá trị ~v_p~ với ~p~ là đỉnh nằm trên đường đi đơn từ đỉnh ~0~ đến đỉnh ~u~ tương tự subtask 2.

Thay vì duyệt tuyến tính như subtask 2 để tìm ra phần tử nhỏ nhất thì ta sẽ thay thế bằng cấu trúc CTDL Trie. Ta quay về bài toán tìm ra giá trị nhỏ nhất sao cho ~A_{0_i} \oplus g_i~ ~(1 \le i \le n)~ là nhỏ nhất

Độ phức tạp : ~O((q + n) . log(A_i))~

Subtask 4

Nếu ta đang có một mảng đã xor với ~g_u~ rồi thêm một phần tử vô, thì ta có thể biến đổi lại là ta đang có mảng ban đầu chưa có xor ~g_u~ rồi thêm một phần tử ~v~ đã xor với ~g_u~. Nếu ta biến đổi vậy, thì ta chỉ cần cài đặt thêm hàm thêm 1 số vào cây trie và bỏ đi một số khỏi cây trie. Ngoài ra, ~ans_u=min(ans_id,v)~.

Nhưng, nếu ta làm vậy thì ta phải thay đổi truy vấn hai từ tìm cặp xor bé nhất trên cây trie với giá trị ~v_i~ thành là tìm cặp xor bé nhất trên cây trie với giá trị là ~v_i \oplus g_i~ để tính cho những giá trị ~g_i~ ta chưa thực hiện xor trên mảng ta đang xét.

Như vậy, thuật toán của ta cũng không thay đổi mấy. Ta vẫn dựng lên một cái cây và dfs trên nó. Nhưng lần này, mỗi cạnh trên cây sẽ biểu hiện cho truy vấn 1 hoặc truy vấn 2. Gọi ~u~ là đỉnh ta đang xét và ~v~ là đỉnh con ta đang xét. Nếu ta gặp cạnh truy vấn 1, ta sẽ để ~ans_v=min(ans_u,v)~. Sau đó, ta sẽ thêm giá trị ~v \oplus g_u~ vào cây trie rồi dfs tiếp, khi ra khỏi đỉnh này thì ta sẽ xoá đi ~v \oplus g_u~ khỏi cây trie. Nếu ta gặp truy vấn 2, ta sẽ để ~ans_v=get(v \oplus g_u)~ với hàm get(x) là hàm tìm cặp xor bé nhất của x với một số trong cây trie. Sau đó, ta sẽ dfs với giá trị ~g_v= g_u \oplus v~mới tương ứng.

Đọ phức tạp thuật toán ~O((n+q)*log_2(A_i))~

Code mẫu: https://ideone.com/K22RYN