## Bquery - Editorial

Thay vì duyệt theo từng $bit$, ta có thể sử dụng các hàm tiện ích ```builtin``` như sau:

- Với truy vấn $1$: dùng ```buitin___builtin_popcount(x)```, hàm này trả về số lượng $bit$ $1$ trong $x$.
- Với truy vấn $2$:
- Nếu $x = 0$ in ra $-1$.
- Ngược lại in ra ```31 - __builtin_clz(x)```.
- Hàm ```__builtin_clz(x)``` miêu tả số $bit$ $0$ ở đầu số $x$ dưới dạng nhị phân, lưu ý là chỉ dùng cho số dạng ```int```, vậy nên ta lấy $31$ trừ đi hàm này.
- Với truy vấn $3$:
- Nếu $x = 0$ in ra $-1$.
- Ngược lại in ra ```__builtin_ctz(x)```. Hàm này miêu tả số $bit$ $0$ ở cuối $x$ dưới dạng nhị phân.

Những hàm tiện ích trên sẽ giúp tối ưu về mặt hệ số hơn là đi tính từng $bit$.

## AndSort - Editorial

### Subtask 1

Ta thử từng $X$ từ $0$ đến $n-1$, rồi thử dùng sắp xếp nổi bọt để kiểm tra.

Độ phức tạp $O(n^3)$.

### Subtask 2

Ta coi dãy $p$ là $p_0,p_1,p_2,...,p_{n-1}$.

Ta nhận thấy rằng, chỉ cần phải dịch chuyển những vị trí $i$ có $p_i \neq i$, như vậy kết quả chính là tập con chung của các $p_i$ này, hay bằng $p_{i0} \& p_{i1} \& p_{i2} \& ... \& p_{ix}$, với $p_{ij}$ là các phần tử thỏa mãn $p_{ij} \neq ij$.

Để tìm tập con này, đầu tiên ta khởi tạo ```res = (1 << 20) - 1```. Nghĩa là khởi tạo kết quả gồm tất cả các $bit$ từ $0->19$ đều bật. Sau đó với $p_i \neq i$, ta thực hiện ```res &= p[i]```.

Kết quả sau cùng chính là biến ```res```.

## MinOp - Editorial

### Subtask 1

Ta quay lui để duyệt tất cả các trường hợp.

Độ phức tạp: $O(2^n)$.

### Subtask 2

Giả sử $S$ là kết quả của bài toán.

Như vậy, ta sẽ luôn có $c_i | S = S$, $\forall 1 \le i \le n$.

Do $a_i,b_i < 2^9$, nên $S < 2^9$.

Vậy, ta có thể duyệt từng giá trị của $S$ từ bé đến lớn để thử, với mỗi $1 \le i \le n$ xem liệu có thể tạo ra $c_i$ sao cho $c_i | S = S$ hay không, nếu tất cả các $i$ đều có thể thì $S$ là giá trị thỏa mãn và ngừng tìm kiếm.

Độ phức tạp: $O(2^9*n*m)$.

## XorAll - Editorial

### Subtask 1

Sinh nhị phân ra toàn bộ các dãy con để tính.

### Subtask 2

Phép $xor$ có tính khử như sau : $a \oplus a = 0$.

Vậy, nếu một giá trị xuất hiện chẵn lần trong phép $xor$, tất cả sẽ bị khử về $0$.

Một phần tử sẽ xuất hiện $2^{n-1}$ lần trong tất cả các dãy con, vậy nếu $n = 1$, kết quả sẽ là $a_1$, ngược lại $n > 1$, tất cả các phần tử sẽ xuất hiện chẵn lần, vậy ta có kết quả là $0$.

## XorTree - Editorial

### Subtask 1

Ta cố đỉnh từng đỉnh $u$ và $dfs$ để tính được hết các $f(u,v)$.

Độ phức tạp: $O(n^2)$.

### Subtask 2

Ta tạm coi "gốc" của cây là $1$. Ta sẽ $dfs$ từ đỉnh $1$ và thu được $lv[u]$ là tổng $xor$ của trọng số cạnh trên đường đi từ $1$ tới $u$.

Lúc này, $f(u,v)$ sẽ bằng $lv[u] \oplus lv[v]$, với $\oplus$ là toán tử $xor$. Ta có thể chứng minh điều này như sau:

- Gọi $c$ là cha chung gần nhất của $u$ và $v$.
- Ta có:
- $f(u,v) = (lv[u] \oplus lv[c]) \oplus (lv[v] \oplus lv[c])$
- $f(u,v) = lv[u] \oplus lv[v] \oplus (lv[c] \oplus lv[c])$
- $f(u,v) = lv[u] \oplus lv[v]$.

Như vậy, với mỗi $u$, ta cần đi tính giá trị của tất cả các $lv[u] \oplus lv[v]$. Tuy vậy, duyệt từng $v$ sẽ không đủ nhanh.

Thay vào đó, ta sẽ tính theo từng $bit$.

Gọi $cnt[i][j]$ $(0 \le i \le 20, 0 \le j \le 1)$ là số lượng đỉnh $u$ với $lv[u]$ có giá trị của $bit$ thứ $i$ là $j$.

Sau khi tính được mảng $cnt$, ta duyệt từng đỉnh $u$, sau đó duyệt từng $bit$ trong $lv[u]$.

Giả sử $bit$ thứ $i$ có giá trị là $1$, ta sẽ cộng vào kết quả $2^i * cnt[i][0]$, bởi nếu $lv[u]$ $xor$ với một $lv[v]$ nào đó chứa $bit$ thứ $i$ bằng $0$, kết quả thu được sẽ có $bit$ thứ $i$ bằng $1$ và đem lại giá trị $2^i$. Ngược lại nếu $lv[v]$ có $bit$ thứ $i$ bằng $1$, kết quả thu được sẽ có $bit$ thứ $i$ bằng $0$ và không đem lại thêm giá trị nào.

Tương tự với trường hợp $bit$ thứ $i$ có giá trị $0$.

Ta có thể thấy rằng, từng $bit$ này độc lập với nhau, nên ta sẽ thu về kết quả đầy đủ.

Độ phức tạp: $O(n*log)$.

## SeqXor - Editorial

### Subtask 1

Sinh nhị phân cả $2$ dãy để kiểm tra.

### Subtask 2

Dựa vào điều kiện:
- $max (i_1, i_2, ..., i_k, j_1, j_2, ..., j_q) - min (i_1, i_2, ..., i_k, j_1, j_2, ..., j_q) = k + q - 1$
- Ta nhận thấy rằng do $max$ và $min$ chỉ số của hai dãy này cách nhau đúng $k + q - 1$ đơn vị, nên chỉ số của hai dãy này cấu thành nên một đoạn con liên tiếp.

Lại có:
- $a_{i1} \oplus a_{i2} \oplus ... \oplus a_{ik} = a_{j1} \oplus a_{j2} \oplus ... \oplus a_{jq}$;
- Như vậy, có thể đổi vế và cho ra tổng $xor$ của hai dãy này bằng $0$.

Vậy, ta có thể duyệt từng đoạn con $[l,r]$ liên tiếp, kiểm tra xem tổng $xor$ của chúng có bằng $0$ hay không, nếu có thì đáp án cộng vào $2^{r-l} - 1$, bởi sẽ có đúng $2^{r-l} - 1$ cách chọn đoạn $[l,r]$ ra hai tập con không rỗng.

Độ phức tạp: $O(n^2)$.
### Subtask 3

Gọi $s_i$ là $prefix$ $xor$ từ $a_1$ tới $a_i$.

Tổng $xor$ trong đoạn $[l,r]$ sẽ là $s_r \oplus s_{l-1}$.

Như vậy ta có thể cải tiến từ $subtask$ $2$ lên như sau:

- Lưu một ```map<int ,ii> mp```.
- Khi duyệt đến một $s_i$, ta cần đi tìm những $s_j$ sao cho $s_j = s_i$, để đoạn $[j+1,i]$ có tổng $xor$ bằng $0$. Các giá trị $j$ này sẽ đóng góp vào kết quả như sau:
- $(2^{(i-j_1 - 1)}-1) + (2^{(i-j_2 - 1)}-1) + ... + (2^{(i-j_k - 1)}-1)$
- Hay: $2^i * (\frac{1}{2^{j_1+1}} + \frac{1}{2^{j_2+1}} + ... + \frac{1}{2^{j_k+1}}) - k$
- Để tính được điều này, ta dùng ```map``` như sau:
- $key$ lưu giá trị $prefix$ $xor$.
- $value.first = \sum inversion(2^{(j+1)})$, với $j$ thỏa mãn $s_j = key$ và $inversion(2^{(j+1)})$ là nghịch đảo module của $2^{(j+1)}$.
- $value.second = count(j)$, hay số lượng số $j$ thỏa mãn $s_j = key$.
- Khi duyệt đến một giá trị $s_i$, ta cộng vào kết quả:
- $add = mp[a[i]].first*2^i - mp[a[i]].second$
- Đồng thời ta thêm vào ```map```:
- $m[a[i]].first += inversion(2^{(i+1)})$.
- $m[a[i]].second += 1$.
- Độ phức tạp: $O(n*log)$.