Giả sử $0 \le A_i \le 1$, chúng ta sẽ làm thế nào?
Ta sẽ dựng một mảng $P$ mới là tổng prefix XOR của mảng $A$, hay nói cách khác: $P_i = A_1 \oplus A_2 \oplus...\oplus A_{i-1} \oplus A_i$ với mọi $1 \le i \le n$. Ta có thể dễ dàng tính mảng $P$ như mảng cộng dồn, hay $P_i = P_{i-1} \oplus A_i$. Lúc này ta có thể dễ dàng tính tổng XOR của một đoạn liên tiếp ($l, r$) bằng công thức $P_r \oplus P_{l-1}$ (**lưu ý** $P_0 = 0$).
Như vậy, với mỗi cặp truy vấn ($l, r$) ta chỉ cần đếm số cặp ($x, y$) sao cho ($l \le x \le y \le r$) và $P_y \oplus P_{x-1} = 1$. Đáp án của việc này cũng chính là số vị trí $j$ trong đoạn [$l-1, r$] mà $P_j = 1$ nhân với số lượng vị trí $k$ mà $P_k = 0$ cũng nằm trong đoạn này. Ta có thể sử dụng **segment tree** để đếm nhanh số lượng $P_j$ thỏa mãn, gọi là $c$, như vậy số lượng $k$ thỏa mãn là $r-l+2-c$, và đáp án cho mỗi truy vấn là $c \cdot (r-l+2-c)$.
Vậy với trường hợp $A_i$ lớn hơn thì ta sẽ làm thế nào? Ta sẽ giải bài toán này với từng bit riêng biệt, vì $1 \le A_i \le 10^9$ nên ta chỉ cần quan tâm đến 30 bit đầu tiên. Với mỗi bit $i$, đếm số lần bit $i$ đóng góp vào đáp án tương tự như trường hợp $0 \le A_i \le 1$, gọi là $cnt_i$, như vậy, đáp án cho mỗi truy vấn là $\sum\limits_{i = 0}^{29} cnt_i \cdot 2^i$. Tổng cộng ta cần 30 segment tree khác nhau cho việc này.
Với truy vấn loại 1, ta cũng sẽ update segment tree của mình với từng bit riêng biệt. Khi xét đến bit thứ $j$, nếu $A_i$ có bit này nhưng $x$ không có, hoặc ngược lại, thì prefix XOR của cả đoạn [$i, n$] ($P_k$ sẽ thay đổi với mọi $i \le k \le n$) sẽ được đảo ngược lại. Vì ta cần update cả một đoạn liên tiếp, nên ta sẽ dùng kĩ thuật **lazy update** trên segment tree, một lần đảo ngược bit của đoạn ($l, r$) tương đương với việc ta **swap** số lần xuất hiện bit 1 và số lần xuất hiện bit 0 trong đoạn này.
Với cách làm trên, tổng độ phức tạp thời gian và không gian là $O(n \cdot \log{_2} n \cdot 30)$.
Code mẫu:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
struct ST
{
int st[4*N][2], lazy[4*N];
void build(int id = 1, int lx = 1, int rx = N-1)
{
if (lx == rx)
{
st[id][0] = 1;
return;
}
int mid = (lx+rx)/2;
build(id*2, lx, mid);
build(id*2+1, mid+1, rx);
st[id][0] = st[id*2][0]+st[id*2+1][0];
}
ST()
{
build();
}
void push(int id, int lx, int rx)
{
if (lazy[id]) swap(st[id][0], st[id][1]);
if (lx != rx)
{
lazy[id*2] ^= lazy[id];
lazy[id*2+1] ^= lazy[id];
}
lazy[id] = 0;
}
void update_range(int l, int r, int id = 1, int lx = 1, int rx = N-1)
{
push(id, lx, rx);
if (l <= lx && rx <= r)
{
lazy[id] ^= 1;
push(id, lx, rx);
return;
}
if (l > rx || lx > r) return;
int mid = (lx+rx)/2;
update_range(l, r, id*2, lx, mid);
update_range(l, r, id*2+1, mid+1, rx);
st[id][0]= st[id*2][0] + st[id*2+1][0];
st[id][1]= st[id*2][1] + st[id*2+1][1];
}
int get(int l, int r, int id = 1, int lx = 1, int rx = N-1)
{
push(id, lx, rx);
if (l <= lx && rx <= r) return st[id][1];
if (l > rx || lx > r) return 0;
int mid = (lx+rx)/2;
return get(l, r, id*2, lx, mid) + get(l, r, id*2+1, mid+1, rx);
}
} bit[30];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
int a[n+1], p[30] = {0};
for (int i = 1; i <= n; i++)
{
cin >> a[i];
for (int j = 0; j < 30; j++)
{
if (a[i]&(1<<j)) p[j] ^= 1;
if (p[j]) bit[j].update_range(i, i);
}
}
while (q--)
{
int type;
cin >> type;
if (type == 1)
{
int i, x;
cin >> i >> x;
for (int j = 0; j < 30; j++)
if ((a[i]&(1<<j)) != (x&(1<<j)))
bit[j].update_range(i, n);
a[i] = x;
} else
{
int l, r;
cin >> l >> r;
long long ans = 0;
for (int j = 0; j < 30; j++)
{
int cnt = bit[j].get(max(l-1, 1), r);
ans += 1ll*cnt*(r-l+2-cnt)*(1<<j);
}
cout << ans << '\n';
}
}
return 0;
}
```
chautanphat
Created at
11 likes