Problem XOR on Segment

Link: http://codeforces.com/problemset/problem/242/E

E. XOR on Segment

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You've got an array a, consisting of n integers a₁, a₂, ..., a_n. You are allowed to perform two operations on this array:

1. Calculate the sum of current array elements on the segment [l, r], that is, count value a_l + a_l + 1 + ... + a_r.
2. Apply the xor operation with a given number x to each array element on the segment [l, r], that is, execute . This operation changes exactlyr - l + 1 array elements.

Expression  means applying bitwise xor operation to numbers x and y. The given operation exists in all modern programming languages, for example in language C++ and Java it is marked as "^", inPascal — as "xor".

You've got a list of m operations of the indicated type. Your task is to perform all given operations, for each sum query you should print the result you get.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the size of the array. The second line contains space-separated integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁶) — the original array.

The third line contains integer m (1 ≤ m ≤ 5·10⁴) — the number of operations with the array. The i-th of the following m lines first contains an integer t_i (1 ≤ t_i ≤ 2) — the type of the i-th query. If t_i = 1, then this is the query of the sum, if t_i = 2, then this is the query to change array elements. If the i-th operation is of type 1, then next follow two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n). If the i-th operation is of type 2, then next follow three integers l_i, r_i, x_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ x_i ≤ 10⁶). The numbers on the lines are separated by single spaces.

Output

For each query of type 1 print in a single line the sum of numbers on the given segment. Print the answers to the queries in the order in which the queries go in the input.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use thecin, cout streams, or the %I64d specifier.

Sample test(s)

input

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

output

26
22
0
34
11

input

6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3

output

38
28

Thuật toán IT trên bit.

Code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdlib>


using namespace std;

#define oo 1000000005
#define rep(i,s,e) for(int i = s; i < e; i++)
#define lop(i,s,e) for(int i = s; i != e; i++)
#define FOR(it,c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define SZ(x) ((int)(x).size())
#define X first
#define Y second
#define N 100005

typedef pair<int,int> II;
typedef pair<II,int> D;
typedef long long LL;

vector<int> V;
map<int,int> M;
set<int> S;
queue<int> Q;
stack<int> ST;


struct IT_Bit_Xor
{
bool rev[4 * N];
int val[4 * N];

void buil(int left, int right, int root, int *b)
{
rev[root] = 0;
if(left == right)
{
val[root] = b[left];
return;
}
int mid = (left + right) >> 1;
buil(left, mid, root << 1, b);
buil(mid + 1, right, (root << 1) + 1, b);
val[root] = val[root << 1] + val[(root << 1) + 1];
}

int get(int left, int right, int root)
{
if(!rev[root]) return val[root];
return (right - left + 1) - val[root];
}

void push(int left, int right, int root)
{
if(!rev[root]) return;
rev[root << 1] ^= 1;
rev[(root << 1) + 1] ^= 1;
rev[root] = 0;
}

void pull(int left, int right, int root)
{
int mid = (left + right) >> 1;
val[root] = get(left, mid, root << 1) + get(mid + 1, right, (root << 1) + 1);
}

int query(int left, int right, int root, int qleft, int qright)
{
if(qleft > right || qright < left) return 0;
if(qleft <= left && right <= qright) return get(left, right, root);
push(left, right, root);
int mid = (left + right) >> 1;
int _res = 0;
_res += query(left, mid, root << 1, qleft, qright);
_res += query(mid + 1, right, (root << 1) + 1, qleft, qright);
pull(left, right, root);
return _res;
}

void change(int left, int right, int root, int qleft, int qright)
{
if(qleft > right || qright < left) return;
if(qleft <= left && right <= qright)
{
rev[root] ^= 1;
return;
}
push(left, right, root);
int mid = (left + right) >> 1;
change(left, mid, root << 1, qleft, qright);
change(mid + 1, right, (root << 1) + 1, qleft, qright);
pull(left, right, root);
}
};

int n, m, a[N], b[N], t, l, r, x;
IT_Bit_Xor bit[20];

int getBit(int x,int i)
{
return ((x >> i) & 1);
}

int main()
{
#define Off  true
if(Off)
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
}

cin >> n;
rep(i, 1, n + 1)
scanf("%d",&a[i]);
rep(i, 0, 20)
{
rep(j, 1, n + 1) b[j] = getBit(a[j],i);
bit[i].buil(1,n,1,b);
}

cin >> m;
rep(i,0,m)
{
scanf("%d",&t);
if(t == 1)
{
scanf("%d %d",&l,&r);
LL res = 0;
rep(i,0,20)
res += (1ll << i) * bit[i].query(1,n,1,l,r);
printf("%I64d\n",res);
}
else
{
scanf("%d %d %d",&l, &r, &x);
rep(i,0,20)
if(getBit(x,i)) bit[i].change(1,n,1,l,r);
}
}
return 0;
}