每一个二进制位建一颗线段树，总共4颗。
然后几个操作：
AND 如果opn在某位上为0，则将这一位的树的[l,r]成段替换为0;
OR 如果opn在某位为1，则将这一位的树的[l,r]成段替换为1；
XOR 一般的异或标记
#include#include #define lson idx << 1, l, mid#define rson idx << 1 | 1, mid + 1, rusing namespace std;const int maxn = 1e6 + 10;int da[maxn];struct SegmentTree { int sum[maxn << 2]; int setv[maxn << 2]; int xorv[maxn << 2]; void PushUp(int idx) { sum[idx] = sum[idx << 1] + sum[idx << 1 | 1]; } void maintain(int idx, int l, int r, int v1, int v2) { if(v1 != -1) { setv[idx] = v1; sum[idx] = (r - l + 1) * v1; xorv[idx] = 0; } if(v2 != 0) { xorv[idx] ^= 1; sum[idx] = r - l + 1 - sum[idx]; } } void PushDown(int idx, int l, int r) { int mid = (r + l) >> 1; maintain(lson, setv[idx], xorv[idx]); maintain(rson, setv[idx], xorv[idx]); setv[idx] = -1; xorv[idx] = 0; } void build(int idx, int l, int r) { setv[idx] = -1; xorv[idx] = 0; if(l == r) sum[idx] = da[l] % 2, da[l] /= 2; else { int mid = (r + l) >> 1; build(lson); build(rson); PushUp(idx); } } void update(int idx, int l, int r, int tl, int tr, int v1, int v2) { if(tl <= l && tr >= r) maintain(idx, l, r, v1, v2); else { PushDown(idx, l, r); int mid = (r + l) >> 1; if(tl <= mid) update(lson, tl, tr, v1, v2); if(tr > mid) update(rson, tl, tr, v1, v2); PushUp(idx); } } int query(int idx, int l, int r, int tl, int tr) { if(tl <= l && tr >= r) return sum[idx]; else { int sum = 0; PushDown(idx, l, r); int mid = (r + l) >>1; if(tl <= mid) sum += query(lson, tl, tr); if(tr > mid) sum += query(rson, tl, tr); return sum; } }}tree[4];int main() { int T; scanf("%d", &T); for(int _t = 1; _t <= T; _t++) { int N, M; scanf("%d%d", &N, &M); for(int i = 1; i <= N; i++) scanf("%d", &da[i]); for(int i = 0; i < 4; i++) tree[i].build(1, 1, N); for(int q = 1; q <= M; q++) { char s[10]; int l, r, v; scanf("%s", s); if(s[0] == 'S') { scanf("%d%d", &l, &r); l++; r++; int ans = 0; for(int i = 0; i < 4; i++) ans += (1 << i) * tree[i].query(1, 1, N, l, r); printf("%d\n", ans); } else { scanf("%d%d%d", &v, &l, &r); l++; r++; for(int i = 0; i < 4; i++, v /= 2) { if(s[0] == 'A' && v % 2 == 0) tree[i].update(1, 1, N, l, r, 0, 0); if(s[0] == 'O' && v % 2 == 1) tree[i].update(1, 1, N, l, r, 1, 0); if(s[0] == 'X' && v % 2 == 1) tree[i].update(1, 1, N, l, r, -1, 1); } } } } return 0;}