Solutions of Mass XOR queries

Select solution language

kevinPhan Created at 2 likes

## KHUYÊN CÁC BẠN NÊN SUY NGHĨ TRƯỚC KHI ĐỌC SOLUTION NHAAA Mình nghĩ bài này không phải dễ nhưng cũng không hẵn khó hơn bài trước, bài này chỉ là tính chất phép XOR thôi nên nhận ra thì phần cài khá đơn giản ## Kiến thức cần - Trie - Xử lý bit ## Ý tưởng - Bài này là về $bit$ nên có thể dễ biết mình cần làm việc với hệ nhị phân những số này - Nếu các bạn đã đến được bài này thì mình xin mặc định là truy vấn 1 và 2 là đã có thể làm - Truy vấn 4 cũng không quá khó, chỉ là đi bộ trên cây Trie. - Nếu bài này chỉ có truy vấn 1, 2, 4 ta có thể làm như sau: - Ta biết mỗi node trên Trie chỉ có tối đa 2 con, là $child[0]$ hoặc $child[1]$. - Khi thêm 1 số vào Trie, ta đi từ $bit$ lớn nhất đến nhỏ nhất (từ trái sang), điều này sẽ khiến việc tính truy vấn 4 dễ hơn nhiều. - Mỗi node ta chỉ cần lưu $cnt[p]$ là số lượng số đi qua $node[p]$ trong Trie. - Truy vấn 1 đơn giản là $++cnt[p]$ và truy vấn 2 là $--cnt[p]$ - Để tính truy vấn 4, giả sử ta cần tìm số nhỏ thứ $k$: - 1/ Bắt đầu ở đỉnh Trie (node 0) - 2/ Ở mỗi node ta có 2 lựa chọn đi xuống $child[0]$ hoặc $child[1]$. Nếu $cnt[child[0]] < k$ nghĩa là có ít hơn k số mà $bit$ tiếp theo là 0 => số ta cần tìm nằm trong $child[1]$, trường hợp này ta gán $k' = k - cnt[child[0]]$ và tìm số nhỏ thứ $k'$ trong $child[1]$. Ngược lại ta đi xuống $child[0]$. - Ta lặp lại bước 2 đến khi chạm đáy hoặc $bit$ đang xét là bit giá trị nhỏ nhất. - Lí do ta làm vậy là do ta đã xây Trie theo giá trị $bit$ giảm dần nghĩa là ta có một tính chất trên cây là mọi node nằm trong $child[0]$ sẽ có giá trị nhỏ hơn $child[1]$. - Nếu bài này chỉ có thế thì rất đơn giản.. tầm 1400 - Bây giờ đến thứ khiến bài này có rating 2000 là truy vấn 3: XOR mọi giá trị trong $S$ cho $x$. - Việc XOR mọi phần tử sẽ tương với vai trò $child[0]$/$child[1]$ bị hoán đổi với mọi node có độ xâu $d$ trong đó $bit$ thứ $d$ của $x = 1$ - Như thế thì quá trâu, tương đương với việc đi qua mọi node của cây với mỗi update, lên đến $O(q * n)$ - hmm...... (Phần sau đây sẽ hơi khó giải thích nên mọi người thông cảm nếu không hiểu) - Ta sẽ lạm dụng tính chất kết hợp và giao hoán của phép XOR - Thay vì coi 2 con là $child[0]$ và $child[1]$ thì ta sẽ coi 2 con đơn giản là... 2 con :) Mình sẽ không mặc định $child$ nào tượng trưng cho giá trị 1/0. - Lí do ta làm vậy là vì XOR đơn giản chỉ hoán đổi vai trò $child[0]$/$child[1]$ nên quan trọng chỉ là trạng thái flip. - Khi cần update thì ta có thể thay đổi giá trị đầu vào. Nói cách khác thay vì áp dụng phép XOR lên cả cái cây thì mình chỉ cần áp phép XOR lên giá trị đang xử lý. - Làm vậy thì trạng thái flip vẫn sẽ được bảo quản. Tức là dù mình không biết bên nào là 0 bên nào là 1, về bản chất 2 bên vẫn lưu đúng giá trị, mình chỉ cần biết trạng thái flip sẽ lấy lại được giá trị cần... hiểu hong :v "mình XOR nhiều lần thì sao?" - Đây lúc áp dụng tính kết hợp của XOR, ta sẽ lưu một biến gọi là $globalXOR$ đi - Đối với truy vấn 3 chỉ cần làm phép $globalXOR ⊕ x$, $globalXOR = x1 ⊕ x2 ⊕ x3 ⊕ x4 ⊕ ...$. - Truy vấn 1, 2 thì chỉ cần làm phép $x ⊕ globalXOR$ trước khi thêm hoặc bỏ giá trị. - Cái này các bạn có thể tự chứng minh vì sao nó đúng - Truy vấn 4 chúng ta sẽ có chút thay đổi: - Dù mình có bảo mình sẽ bỏ nhãn 0/1 cho $child$ mình vẫn cần biết ban đầu cái nào là 0 cái nào là 1 - Khi query thì thông thường ta sẽ check $cnt[child[0]]$ có đủ $k$ không, nhưng do đã XOR nhiều lần nên node thể hiện cho số lượng số có $child0$ đã hoán đổi nhiều lần. - Ta đặt $bit0$ trỏ tới node con lưu giá trị này, ta sẽ mặc định $bit0 = 0$. Có thể thấy $child[0]$ và $child[1]$ có bị swap hay không sau mọi phép XOR trước phụ thuộc vào $bit$ thứ $depth$ của $globalXOR$ - Vậy $child$ đang tượng trưng cho giá trị 0 hiện tại sẽ là $bit0 = 0 ⊕ globalXOR >> depth$ hoặc đơn giản là $bit0 = globalXOR >> depth$. - Khi biết cái nào là $child[0]$ hiển nhiên con còn lại là $child[1]$ từ đó ta có thể truy vấn như bình thường ## Cách cài Thật ra có ý tưởng thì cách cài cũng chả có gì cả -.- - Ta khai báo một biến chứa giá trị XOR chung. - Tạo một Trie lưu biến đếm số lần đi qua một node. - Trước khi thêm hoặc bỏ 1 giá trị, cần XOR nó với $globalXOR$. - Truy vấn 3 đơn giản là $globalXOR ⊕ x$ - Truy vấn 4 thực hiện như trên ## [END]