Lời giải được cung cấp bởi bạn nguyen31hoang08minh2003

Tóm tắt đề bài

• Cho một mảng ~A~ gồm ~n~ phần tử. Hãy kiểm tra từng tiền tố ~[A[0], ..., A[k - 1]]~ của mảng ~A~ (~1 \leq k \leq n~) có tồn tại một hoán vị ~[C[0], ..., C[k - 1]]~ sao cho tổng xor tiền tố của ~C~ tăng dần (nếu ta đặt ~P[0] = C[0]~ và ~P[i] = P[i - 1] \oplus C[i]~ với ~1 \leq i < k~ thì ta có ~P[i] > P[i - 1]~ với mọi ~i~ sao cho ~1 \leq i < k~).

Ý tưởng

• Để dễ hình dung, ta hãy trước tiên xét bài toán kiểm tra một mảng có thể được coi là "đẹp" không. Ta gọi số ~a~ có bit ~b~ ở hàng ~i~ nếu bit thứ ~i~ từ phải sang trái trong biểu diễn nhị phân của ~a~ có giá trị bằng ~b~ (~b \in \{0, 1\}~, ~i \in N~) và MSB (most significant bit) của ~a~ là bit tận cùng bên trái trong biểu diễn nhị phân của ~a~ không chứa bit ~0~ vô nghĩa ở đầu.

• Ta có thể kiểm tra một dãy số có "đẹp" hay không bằng cách xem xét từng hàng (cụ thể hơn, ta chỉ cần xét các hàng từ ~29~ tới ~0~ trong bài toán này do một phần tử của mảng ~A~ có tối đa có ~30~ bit có nghĩa), nếu như số phần tử có MSB ở hàng đang xét nhiều hơn một phần tử số phần tử có bit ~1~ ở hàng đang xét nhưng không chứa MSB hàng đang xét đó thì mảng đó sẽ không "đẹp". Ngược lại, ta có thể kết luận dãy số đó "đẹp".

  Ta có thể chứng minh rằng nếu cách kiểm tra trên thỏa thì dãy số sẽ "đẹp" bằng cách chứng minh quy nạp: ta gọi ~R[b]~ là dãy các phần tử thuộc ~A~ mà có MSB ở hàng không nhỏ hơn ~b~, ta sẽ xét trường hợp đầu tiên ở hàng cao nhất và ta muốn chứng minh là ~R[0]~ là dãy số "đẹp".

  Ví dụ

  Giả sử ta có ~n = 5~ và ~A~ gồm các phần tử ~1~ (tức ~1_2~), ~5~ (tức ~101_2~), ~2~ (tức ~10_2~), ~7~ (tức ~111_2~), ~8~ (tức ~1000_2~) thì ~R[3]~ gồm duy nhất số ~8~ ~R[2]~ gồm số ~5~, ~7~ và ~8~ ~R[1]~ gồm số ~2~, ~5~, ~7~ và ~8~ ~R[0]~ gồm số ~1~, ~2~, ~5~, ~7~ và ~8~ Với ~b \in N~ và ~b > 3~, ~R[b]~ không chứa số nào

  • Giả sử ~b~ là hàng cao nhất mà ~R[b]~ khác rỗng, tức ~R[b + 1]~ rỗng. Vì thế ~R[b]~ có duy nhất một phần tử và đương nhiên là dãy số "đẹp".

  • Giả sử ~R[b]~ là dãy số đẹp (~b \geq 1~) và hàng ~b - 1~ thỏa điều kiện đã nêu, ta có thể tìm được một hoán vị của ~R[b - 1]~ thỏa yêu cầu đã nêu. Gọi ~[X[0], ..., X[m]]~ là dãy các phần tử thuộc ~R[b - 1]~ nhưng không thuộc ~R[b]~ và ~[Y[0], ..., Y[k]]~ là dãy các phần tử còn lại được sắp xếp theo hoán vị thỏa điều kiện của ~R[b]~. Ta có thể chọn cách sắp xếp như sau ~[X[0], Y[0], X[1], Y[1], ..., X[m], Y[m], Y[m + 1], ..., Y[k - 1], Y[k]]~

    Giải thích

    Trong một cách sắp xếp ~[C[0], ..., C[k - 1]]~ thỏa điều kiện, ta có thể chứng minh ~P[i] = C[0] \oplus ... \oplus C[k - 1]~ tạo thành một dãy tăng nghiêm ngặt.

    Vì không có phần tử nào bằng không nên ~P[i - 1] \neq P[i]~ với mọi ~i \geq 1~.

    Với cách sắp xếp như vậy, khi ta xét vị trí ~i~, nếu như ~C[i]~ thuộc ~R[b]~ thì ~P[i]~ sẽ luôn lớn hơn ~P[i - 1]~ bởi các phần tử chỉ thuộc ~R[b - 1]~ chỉ làm "tác động" tới các hàng nhỏ hơn ~b~ và các phần cũng thuộc ~R[b]~ được sắp xếp theo hoán vị thỏa điều kiện của ~R[b]~. Nếu như ~C[i]~ không thuộc ~R[b]~ thì cách sắp xếp như trên đảm bảo bit ở hàng ~b~ của ~P[i - 1]~ là bit ~0~, khiến bit ở hàng ~b~ của ~P[i]~ là bit ~1~ (trong khi các bit ở hàng lớn hơn của ~P[i]~ sẽ giống với bit của ~P[i - 1]~).

  Ngược lại, ta cũng có thể chứng minh là nếu điều kiện trên không thỏa thì dãy số không "đẹp".

  Chứng minh

  Ta gọi ~b~ là hàng cao nhất mà điều kiện trên không thỏa. Lúc này, trong bất kì hoán vị ~[C[0], ..., C[k - 1]]~ nào của ~R[b]~, cũng sẽ luôn tồn tại hai vị trí ~i~ và ~j~ sao cho ~i < j~, ~C[i]~ và ~C[j]~ thuộc ~R[b]~ nhưng không thuộc ~R[b + 1]~, không tồn tại bất kì vị trí ~z~ nào mà ~i < z < j~ và bit ở hàng ~b~ của ~C[z]~ là bit ~1~ (Pigeonhole principle). Lúc này, ~P[j]~ sẽ nhỏ hơn ~P[j - 1]~ hoặc ~P[i]~ sẽ nhỏ hơn ~P[i - 1]~ (do số sau có bit ở hàng ~b~ là bit ~0~ trong khi số số trước có bit ở hàng ~b~ là bit ~1~, cùng với đó là trong các hàng lớn hơn, hai số có cùng bit).

  Vì ~R[b]~ không "đẹp" nên cũng sẽ dẫn tới ~R[0]~ không "đẹp".

• Ta để ý rằng việc kiểm tra chỉ cần yêu cầu ta đếm bit một của các phần tử ở mỗi hàng nhị phân nên nếu ta muốn thêm một số vào dãy số hiện tại và kiểm tra xem dãy số mới có "đẹp" hay không, ta chỉ cần cập nhật mảng đếm bit một của dãy số cũ. Dựa vào ý tưởng này, ta có thể kiểm tra mọi tiền tố của dãy số được cho có "đẹp" hay không trong thời gian cho phép.

Độ phức tạp thời gian

• Ta chỉ cần duyệt các phần tử của dãy số được cho theo thứ tự từ vị trí nhỏ đến vị trí lớn và với mỗi vị trí đang duyệt, ta cập nhật mảng đếm và thực hiện kiểm tra bằng cách duyệt các hàng nhị phân của phần tử thuộc vị trí đó. Vì vậy thuật toán đã nêu có độ phức tạp ~O(n \log a)~ với ~a~ là giá trị lớn nhất mà một phần tử của mảng ~A~ có thể có (tức ~a~ có giá trị ~2^{30} - 1~).

Cài đặt

#include <bits/stdc++.h>

using namespace std;

constexpr int MAX_N = 2E5 + 5;

signed main() {

    int n, A[MAX_N]{}, oneCount[32]{}, notFirstOneCount[32]{};
    bool result, first;

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0, e; i < n; ++i) {
        cin >> A[i];
        result = first = true;
        for (e = 30; e >= 0; --e) {
            if (A[i] & (1 << e)) {
                ++oneCount[e];
                if (first)
                    first = false;
                else
                    ++notFirstOneCount[e];
            }
            if (oneCount[e] - notFirstOneCount[e] > notFirstOneCount[e] + 1)
                result = false;
        }
        puts(result ? "YES" : "NO");
    }

    return 0;
}