# **Phân tích và Giải pháp bài toán XOR (marisaoj.com/problem/688)**

### **1. Hướng tiếp cận**

> **Hướng tiếp cận:** (Giải thích thì dài, nhma code siêu gọn🐧)
>
> **Tóm gọn mục tiêu:** Tìm các cặp `(i, j)` sao cho: $$a_i \le (a_i \oplus a_j) \le a_j$$
>
> - Bài này đếm cặp => ta ưu tiên **sort** lại để đếm.
>
> **Lưu ý 2 tính chất quan trọng:**
> - $2^k > \sum_{p=0}^{k-1} 2^p$ (Bit lớn nhất quyết định độ lớn của số).
> - `1 ⊕ 1 = 0` (Phép XOR có thể "tắt" bit).

Sau khi sắp xếp, bài toán chuyển thành: Với mỗi `y = a[j]`, ta cần tìm số lượng `x = a[i]` (với `i ≤ j`) thỏa mãn $x \le (x \oplus y) \le y$.

---

### **2. Phân tích & Chứng minh**

Ta cần thỏa mãn đồng thời 2 điều kiện:
1. `(x ⊕ y) ≤ y`: Để kết quả không lớn hơn `y`, phép XOR phải "tắt" ít nhất một bit `1` của `y`. Điều này chỉ xảy ra khi `x` có chung một bit `1` nào đó với `y`.
2. `x ≤ (x ⊕ y)`: Đây là điều kiện khó hơn.

> **Chứng minh bằng ví dụ:**
>
> - **Trường hợp sai:** Nếu `MSB(x)` (bit 1 cao nhất của `x`) trùng với `MSB(y)`.
> - Ví dụ: `y = 169 (10101001)`, `x = 128 (10000000)`.
> - `MSB(x) = MSB(y) = 7`.
> - `x ⊕ y = 41 (00101001)`.
> - Ta thấy `41 < 128`, tức là `(x ⊕ y) < x`. **Không thỏa mãn.**
> - *Lý do:* Khi tắt đi bit quan trọng nhất, giá trị của số sẽ giảm mạnh, nhỏ hơn cả `x` ban đầu.
>
> - **Trường hợp đúng:** Để `x ≤ (x ⊕ y)`, `MSB(y)` phải được giữ nguyên trong phép XOR. Điều này có nghĩa là bit tại vị trí `MSB(y)` của `x` phải là `0` (luôn đúng khi `x < y`).
>
> **Kết hợp lại:**
>
> Để thỏa mãn cả 2 điều kiện, `x` phải "tắt" một bit nào đó của `y` nhưng không được đụng đến `MSB(y)`.
>
> => **Điều kiện cuối cùng:** `MSB(x)` phải trùng với một trong các bit `1` của `y`, **ngoại trừ** bit `MSB(y)`.
>
> Nói cách khác:
>
> > Với mỗi `y = a[j]`, ta chỉ cần tìm số lượng `x = a[i]` (`i < j`) sao cho `MSB(x)` trùng với một trong các bit từ **"vị trí 1 lớn nhì"** trở xuống của `y`.

---

### **3. Thuật toán & Code**

- Sắp xếp mảng `a`.
- Duyệt qua từng phần tử `y = a[i]`.
- Với mỗi `y`, ta duyệt qua các vị trí bit `k` của nó (từ bit 1 lớn nhì trở xuống).
- Nếu bit `k` của `y` đang bật, ta đếm xem đã có bao nhiêu số `x` đứng trước có `MSB(x) = k`.
- Dùng mảng `save[]` để lưu tần suất xuất hiện của các `MSB`. `save[k+1]` lưu số lượng số có `MSB` tại vị trí `k`.

> **CÁCH TÌM VỊ TRÍ BIT LỚN NHẤT CỦA 1 SỐ X:** `__lg(x)`

**Code tham khảo:**

#include <bits/stdc++.h>
// Hàm tìm MSB, nếu x=0 thì trả về -1 để tiện xử lý
#define log2(x) ((x <= 0) ? -1 : __lg(x))
#define FOR(i, l, r, x) for(int i = l; i <= r; i += x)
#define FOD(i, l, r, x) for(int i = l; i >= r; i -= x)
#define pii pair<int, int>
#define fi first
#define se second
#define int long long
using namespace std;

const int N = 5e5 + 5;
const int mod = 1e9 + 7;

int n, a[N], save[N];

// Hàm tìm vị trí bit 1 lớn nhì
int bit2nd(int n) {
    int inx = log2(n); // Tìm bit lớn nhất
    if (inx == -1) return -1;
    n ^= (1 << inx);   // Tắt bit lớn nhất đi
    return log2(n);    // Tìm bit lớn nhất của số còn lại
}

// Kiểm tra bit thứ i của mask có bật không
bool isOn(int mask, int i) {
    return ((mask >> i) & 1);
}

void solve() {
    cin >> n;
    FOR(i, 1, n, 1) {
        cin >> a[i];
    }

    // Sắp xếp để đảm bảo khi xét a[i], các số đứng trước luôn nhỏ hơn hoặc bằng
    sort(a + 1, a + n + 1);

    int ans = 0;

    // Duyệt qua mảng, coi a[i] là y (phần tử lớn hơn trong cặp)
    FOR(i, 1, n, 1) {
        int y = a[i];

        // Tối ưu: chỉ cần xét các bit của y lên tới bit 1 lớn nhì của nó
        int pos = bit2nd(y) + 1; /* Đoạn này +1 là do ta phải nhường 
    slot cho trường hợp y = 0 (hay a[i] = 0) (do log2(0) sẽ không xác định)*/

        // Xử lý cặp (y, y). Nếu y=0, đây là cặp (0,0).
        // Nếu y>0, đây là cặp (y,y) cũng luôn hợp lệ.
        // Code gốc gộp lại: nếu y=0 thì ++ans, các cặp (0,0) sau sẽ được đếm ở save.
        if (y == 0) {
            ++ans;
        }

        // Duyệt qua các khả năng cho MSB của x (phần tử nhỏ hơn).
        // j là log2(x) + 1
        FOR(j, 0, pos, 1) {
            // Trường hợp x = 0. Cặp (0, y) luôn hợp lệ.
            if (j == 0) {
                ans += save[j]; // Cộng tất cả các số 0 đã gặp
                continue;
            }

            // Đây là điều kiện cốt lõi từ chứng minh:
            // Kiểm tra xem bit tại vị trí MSB của x (tức là j-1)
            // có được bật trong y (tức là a[i]) hay không.
            if (isOn(y, j - 1)) {
                // Nếu có, tất cả các số x đã gặp có MSB tại vị trí đó đều tạo cặp hợp lệ.
                ans += save[j];
            }
        }

        // Cập nhật: "ghi nhớ" sự xuất hiện của y (a[i]) cho các vòng lặp sau.
        // save[k+1] lưu số lượng số có MSB tại vị trí k.
        save[log2(y) + 1] ++;
    }

    cout << ans << '\n';
}

signed main() {
    #define name "task"
    if (ifstream(name".inp")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();
}