Hướng dẫn cho Codeforces 617E - XOR và số yêu thích
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
XOR tiền tố
Đặt \(P_0=0\), \(P_i=P_{i-1}\oplus a_i\). XOR của đoạn \([i,j]\) bằng \(P_{i-1}\oplus P_j\). Vì vậy truy vấn \([l,r]\) trở thành đếm cặp vị trí khác nhau trong đoạn tiền tố \([l-1,r]\) có XOR bằng \(k\).
Di chuyển hai đầu đoạn bằng Mo
Sắp các truy vấn theo khối của đầu trái; trong mỗi khối, sắp đầu phải tăng hoặc giảm xen kẽ. Giữ cnt[x], số lần giá trị \(x\) có mặt trong đoạn đang xét, và answer, số cặp hợp lệ.
- Thêm giá trị \(x\): cộng
cnt[x ^ k]vào đáp án, rồi tăngcnt[x]. - Bỏ giá trị \(x\): giảm
cnt[x]trước, rồi trừcnt[x ^ k]khỏi đáp án.
Thứ tự ở bước bỏ rất quan trọng khi \(k=0\): vị trí đang bỏ không được ghép với chính nó. Ban đầu đoạn rỗng; mỗi truy vấn đưa hai đầu tới đúng \([l-1,r]\). Lưu kết quả theo mã truy vấn để in theo thứ tự ban đầu.
Vì sao cập nhật đáp án đúng?
Khi thêm một vị trí có giá trị \(x\), mọi cặp mới chứa vị trí này. Giá trị ở vị trí còn lại phải là \(x\oplus k\), và có đúng cnt[x ^ k] lựa chọn. Khi bỏ, ta xóa vị trí khỏi tần suất trước; số cặp mất đi chính là số vị trí còn lại mang giá trị \(x\oplus k\). Các cặp không chứa vị trí vừa thay đổi giữ nguyên.
Với độ dài khối \(B\), số bước di chuyển là \(O(mB+n^2/B)\), ngoài \(O(m\log m)\) để sắp xếp. Chọn \(B\) khoảng \(n/\sqrt m\) cho thời gian \(O(n\sqrt m+m\log m)\), thường viết \(O((n+m)\sqrt n)\) khi \(m\) gần \(n\).
Mọi giá trị dùng ít hơn \(20\) bit, nên có thể dùng mảng tần suất \(2^{20}\) ô. Bộ nhớ \(O(n+m+2^{20})\). Đáp án có thể là \(n(n+1)/2\), cần long long trong C++. Python có cùng số bước nhưng vòng lặp Mo lớn hơn nhiều so với \(O(n\log n)\).
Mã tham khảo
#include <bits/stdc++.h>
using namespace std;
struct Query { int l, r, id, block; };
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, k; if (!(cin >> n >> m >> k)) return 0;
vector<int> prefix(n + 1);
for (int i = 1, x; i <= n; ++i) { cin >> x; prefix[i] = prefix[i-1] ^ x; }
int B = max(1, int((n + 1) / sqrt(double(m))));
vector<Query> queries(m);
for (int i = 0; i < m; ++i) {
int l, r; cin >> l >> r; --l;
queries[i] = {l, r, i, l / B};
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
if (a.block != b.block) return a.block < b.block;
return a.block & 1 ? a.r > b.r : a.r < b.r;
});
vector<int> cnt(1 << 20);
vector<long long> answers(m);
long long answer = 0;
int L = 0, R = -1;
auto add = [&](int pos) { int x=prefix[pos]; answer += cnt[x ^ k]; ++cnt[x]; };
auto remove = [&](int pos) { int x=prefix[pos]; --cnt[x]; answer -= cnt[x ^ k]; };
for (const Query& q : queries) {
while (L > q.l) add(--L);
while (R < q.r) add(++R);
while (L < q.l) remove(L++);
while (R > q.r) remove(R--);
answers[q.id] = answer;
}
for (long long x : answers) cout << x << '\n';
}
import math
import sys
def solve(data):
n, m, k = data[:3]
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i - 1] ^ data[i + 2]
partner = [x ^ k for x in prefix]
B = max(1, int((n + 1) / math.sqrt(m)))
queries = []
pos = n + 3
for query_id in range(m):
l, r = data[pos] - 1, data[pos + 1]
block = l // B
queries.append((block, -r if block & 1 else r, l, r, query_id))
pos += 2
queries.sort()
cnt = [0] * (1 << 20)
answers = [0] * m
L, R, answer = 0, -1, 0
for _, _, l, r, query_id in queries:
while L > l:
L -= 1
answer += cnt[partner[L]]
cnt[prefix[L]] += 1
while R < r:
R += 1
answer += cnt[partner[R]]
cnt[prefix[R]] += 1
while L < l:
cnt[prefix[L]] -= 1
answer -= cnt[partner[L]]
L += 1
while R > r:
cnt[prefix[R]] -= 1
answer -= cnt[partner[R]]
R -= 1
answers[query_id] = answer
return '\n'.join(map(str, answers)) + '\n'
if __name__ == '__main__':
sys.stdout.write(solve(list(map(int, sys.stdin.buffer.read().split()))))
Bình luận