## Description:

Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:

Operation 1: AND opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).

Operation 2: OR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).

Operation 3: XOR opn L R

Here opn, L and R are integers.

For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).

Operation 4: SUM L R

We want to know the result of A[L]+A[L+1]+...+A[R].

Now can you solve this easy problem?

## Input:

The first line of the input contains an integer T, indicating the number of test cases. (T≤100)

Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.

Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).

Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)

## Output:

For each test case and for each "SUM" operation, please output the result with a single line.

1
4 4
1 2 4 7
SUM 0 2
XOR 5 0 0
OR 6 0 3
SUM 0 2

7
18

## Hint:

A = [1 2 4 7]

SUM 0 2, result=1+2+4=7;

XOR 5 0 0, A=[4 2 4 7];

OR 6 0 3, A=[6 6 6 7];

SUM 0 2, result=6+6+6=18.

### 题目链接

1. SUM l r 求 $\sum_{i=l}^{r}a_{i}$
2. AND opn l r $\forall a_i (i \in [l,r]) a_i=a_i \& opn$
3. OR opn l r $\forall a_i (i \in [l,r]) a_i=a_i|opn$
4. XOR opn l r $\forall a_i (i \in [l,r]) a_i=a_i \oplus opn$

## AC代码:

#include <cstdio>
const int maxn = 1e6 + 5;
const int maxdigit = 4;
struct SegTree {
int n;
int sum[maxdigit][maxn * 4];
int lazy[maxdigit][maxn * 4];
bool rev[maxdigit][maxn * 4];
void Push(int o, int l, int r, int dgt) {
int m = (l + r) / 2;
if (lazy[dgt][o] != -1) {
int f = lazy[dgt][o];
if (f) {
sum[dgt][o * 2] = m - l + 1;
sum[dgt][o * 2 + 1] = r - m;
lazy[dgt][o * 2] = lazy[dgt][o * 2 + 1] = 1;
rev[dgt][o * 2] = rev[dgt][o * 2 + 1] = 0;
}
else {
sum[dgt][o * 2] = sum[dgt][o * 2 + 1] = 0;
lazy[dgt][o * 2] = lazy[dgt][o * 2 + 1] = 0;
rev[dgt][o * 2] = rev[dgt][o * 2 + 1] = 0;
}
lazy[dgt][o] = -1;
}
if (rev[dgt][o] != 0) {
sum[dgt][o * 2] = m - l + 1 - sum[dgt][o * 2];
sum[dgt][o * 2 + 1] = r - m - sum[dgt][o * 2 + 1];
rev[dgt][o * 2] ^= 1;
rev[dgt][o * 2 + 1] ^= 1;
rev[dgt][o] = 0;
}
}
void Build(int o, int l, int r, int arr[]) {
for (int dgt = 0; dgt < maxdigit; ++dgt) {
lazy[dgt][o] = -1;
rev[dgt][o] = 0;
}
if (l == r) {
for (int dgt = 0; dgt < maxdigit; ++dgt) sum[dgt][o] = (bool)(arr[l] & (1 << dgt));
return;
}
int m = (l + r) / 2;
Build(o * 2, l, m, arr);
Build(o * 2 + 1, m + 1, r, arr);
for (int dgt = 0; dgt < maxdigit; ++dgt) sum[dgt][o] = sum[dgt][o * 2] + sum[dgt][o * 2 + 1];
}
void Init(int _n, int arr[]) {
n = _n;
Build(1, 1, n, arr);
}
void Modify(int o, int l, int r, int ll, int rr, int dgt, int f) {
if (ll <= l && rr >= r) {
if (f == 1) {
sum[dgt][o] = lazy[dgt][o] = rev[dgt][o] = 0;
}
else if (f == 2) {
sum[dgt][o] = r - l + 1;
lazy[dgt][o] = 1;
rev[dgt][o] = 0;
}
else if (f == 3) {
sum[dgt][o] = r - l + 1 - sum[dgt][o];
rev[dgt][o] ^= 1;
}
return;
}
Push(o, l, r, dgt);
int m = (l + r) / 2;
if (ll <= m) Modify(o * 2, l, m, ll, rr, dgt, f);
if (rr > m) Modify(o * 2 + 1, m + 1, r, ll, rr, dgt, f);
sum[dgt][o] = sum[dgt][o * 2] + sum[dgt][o * 2 + 1];
}
void Modify(int ll, int rr, int dgt, int f) {
Modify(1, 1, n, ll, rr, dgt, f);
}
int Query(int o, int l, int r, int ll, int rr) {
if (ll <= l && rr >= r) {
int ret = 0;
for (int dgt = maxdigit - 1; dgt >= 0; --dgt) ret = (ret << 1) + sum[dgt][o];
return ret;
}
for (int dgt = 0; dgt < maxdigit; ++dgt) Push(o, l, r, dgt);
int m = (l + r) / 2, ret = 0;
if (ll <= m) ret += Query(o * 2, l, m, ll, rr);
if (rr > m) ret += Query(o * 2 + 1, m + 1, r, ll, rr);
return ret;
}
int Query(int ll, int rr) {
return Query(1, 1, n, ll, rr);
}
};
int t;
int n, m;
int a[maxn];
SegTree tree;
int main() {
scanf("%d", &t);
for (int cas = 1; cas <= t; ++cas) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
tree.Init(n, a);
for (int i = 1; i <= m; ++i) {
char op[4];
scanf("%s", op);
if (op[0] == 'S') {
int l, r;
scanf("%d%d", &l, &r);
++l; ++r;
printf("%d\n", tree.Query(l, r));
}
else if (op[0] == 'A') {
int opn, l, r;
scanf("%d%d%d", &opn, &l, &r);
++l; ++r;
for (int dgt = 0; dgt < maxdigit; ++dgt) {
if (!(opn & (1 << dgt))) tree.Modify(l, r, dgt, 1);
}
}
else if (op[0] == 'O') {
int opn, l, r;
scanf("%d%d%d", &opn, &l, &r);
++l; ++r;
for (int dgt = 0; dgt < maxdigit; ++dgt) {
if (opn & (1 << dgt)) tree.Modify(l, r, dgt, 2);
}
}
else if (op[0] == 'X') {
int opn, l, r;
scanf("%d%d%d", &opn, &l, &r);
++l; ++r;
for (int dgt = 0; dgt < maxdigit; ++dgt) {
if (opn & (1 << dgt)) tree.Modify(l, r, dgt, 3);
}
}
}
}
return 0;
}
Last modification：September 13th, 2019 at 02:10 pm