Problem 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
Sample Input
Sample Output
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.
代码如下：
#include#include const int N = 1000005;int c, res, a[N*4][4], flag[N*4][4], len[N*4];void pushDown( int rt ){ int ls = 2 * rt; int rs = ls | 1; for( int i = 0; i < 4; ++i ) { if( flag[rt][i] == -1 ) continue; if( flag[rt][i] == 0 || flag[rt][i] == 1 ) { a[ls][i] = ( flag[ls][i] = flag[rt][i] ) * len[ls]; a[rs][i] = ( flag[rs][i] = flag[rt][i] ) * len[rs]; flag[rt][i] = -1; } else if( flag[rt][i] == 3 ) { flag[rt][i] = -1; } else { a[ls][i] = len[ls] - a[ls][i]; if( flag[ls][i] == -1 ) flag[ls][i] = 2; else flag[ls][i] ^= 1; a[rs][i] = len[rs] - a[rs][i]; if( flag[rs][i] == -1 ) flag[rs][i] = 2; else flag[rs][i] ^= 1; flag[rt][i] = -1; } }}void pushUp( int rt ){ int ls = 2 * rt; int rs = ls | 1; for( int i = 0; i < 4; ++i ) a[rt][i] = a[ls][i] + a[rs][i];}void build( int l, int r, int rt ){ len[rt] = r - l + 1; if( l == r ) { scanf("%d", &c); for( int i = 0; i < 4; ++i ) a[rt][i] = ( 1 & (c>>i) ); } else { int mid = ( l + r ) / 2; build(l, mid, 2 * rt); build(mid + 1, r, 2 * rt + 1); pushUp( rt ); }}void OR( int rt, int opn ){ for( int i = 0; i < 4; ++i ) { if( !( (opn>>i) & 1 ) ) continue; flag[rt][i] = 1; a[rt][i] = len[rt]; }}void ADD( int rt, int opn ){ for( int i = 0; i < 4; ++i ) { if( (opn>>i) & 1 ) continue; flag[rt][i] = 0; a[rt][i] = 0; }}void XOR( int rt, int opn ){ for( int i = 0; i < 4; ++i ) { if( !( (opn>>i) & 1 ) ) continue; if( flag[rt][i] == -1 ) flag[rt][i] = 2; else flag[rt][i] ^= 1; a[rt][i] = len[rt] - a[rt][i]; }}void query( int l, int r, int rt, const int aa, const int bb ){ if( aa <= l && r <= bb ) { res = res + a[rt][0] + a[rt][1] * 2 + a[rt][2] * 4 + a[rt][3] * 8; return; } pushDown( rt ); int mid = ( l + r ) / 2; int ls = 2 * rt; int rs = ls | 1; if( mid >= aa ) query( l, mid, ls, aa, bb ); if( mid < bb ) query( mid + 1, r, rs, aa, bb );}void update( int l, int r, int rt, const int aa, const int bb, const int opn, const int f ){ if( aa <= l && r <= bb ) { switch( f ) { case 0: OR( rt, opn ); break; case 1: ADD( rt, opn ); break; case 2: XOR( rt, opn ); break; } return; } pushDown( rt ); int mid = ( l + r ) / 2; int ls = 2 * rt; int rs = ls | 1; if( mid >= aa ) update( l, mid, ls, aa, bb, opn, f ); if( mid < bb ) update( mid + 1, r, rs, aa, bb, opn, f ); pushUp( rt );}int main(){ int t, n, m, aa, bb, opn; char cmd[4]; scanf("%d", &t); while( t-- ) { memset( flag, -1, sizeof(flag) ); scanf("%d%d", &n, &m); build(0, n-1, 1); while( m-- ) { scanf("%s", cmd); if( cmd[0] == 'S' ) { scanf("%d%d", &aa, &bb); res = 0; query( 0, n - 1, 1, aa, bb ); printf("%d\n", res); } else { scanf("%d%d%d", &opn, &aa, &bb); switch( cmd[0] ) { case 'O': update(0, n-1, 1, aa, bb, opn, 0); break; case 'A': update(0, n-1, 1, aa, bb, opn, 1); break; case 'X': update(0, n-1, 1, aa, bb, opn, 2); break; default : break; } } } } return 0;}