2014
06-24

codeforces-XOR on Segment[线段树]

E. XOR on Segment

You’ve got an array a, consisting of n integers a1, a2, …, an. 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 al + al + 1 + … + ar.
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 exactly r - 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 “^”, in Pascal — 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 ≤ 105) — the size of the array. The second line contains space-separated integers a1, a2, …, an (0 ≤ ai ≤ 106) — the original array.

The third line contains integer m (1 ≤ m ≤ 5·104) — the number of operations with the array. The i-th of the following m lines first contains an integer ti (1 ≤ ti ≤ 2) — the type of the i-th query. If ti = 1, then this is the query of the sum, if ti = 2, then this is the query to change array elements. If the i-th operation is of type 1, then next follow two integers li, ri (1 ≤ li ≤ ri ≤ n). If the i-th operation is of type 2, then next follow three integers li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106). 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 the cin, coutstreams, 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

1 求和操作就是将每位数都拆成 20 位二进制数，后统计每位有多少个 1，然后乘以 2 ^ i，再求和得出的这个数就是求和操作的结果；

2 异或操作，当异或 0 的时候不改变状态，若异或 1 则对区间内的 0 和 1 个数倒转，因为 0 xor 1 = 1,1 xor 1 = 0。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAX = 100005;

int n, dim, s, e, cha;
int num[MAX];
int tree[25][MAX * 5], flag[25][MAX * 5];

ll res;

void Build(int k, int fro, int to) {
int mid = (fro + to) / 2;
flag[dim][k] = 0;
if (fro == to) {
tree[dim][k] = (num[fro] >> dim) & 1;
return;
}
Build(k * 2, fro, mid);
Build(k * 2 + 1, mid + 1, to);
tree[dim][k] = tree[dim][2 * k] + tree[dim][2 * k + 1];
}

void Sum(int k, int fro, int to) {
int mid = (fro + to) / 2;
if (to < s || fro > e) return;
if (fro >= s && to <= e) {
res += tree[dim][k];
return;
}
if (flag[dim][k]) {
flag[dim][k] = 0;
flag[dim][k * 2] = 1 - flag[dim][k * 2];
flag[dim][k * 2 + 1] = 1 - flag[dim][k * 2 + 1];
tree[dim][k * 2] = mid - fro + 1 - tree[dim][k * 2];
tree[dim][k * 2 + 1] = to - mid - tree[dim][k * 2 + 1];
}
Sum(k * 2, fro, mid);
Sum(k * 2 + 1, mid + 1, to);
}

void Xor(int k, int fro, int to) {
int mid = (fro + to) / 2;
if (s > to || e < fro) return;
if (s <= fro && e >= to) {
flag[dim][k] = 1 - flag[dim][k];
tree[dim][k] = to - fro + 1 - tree[dim][k];
return;
}
if (flag[dim][k]) {
flag[dim][k] = 0;
flag[dim][k * 2] = 1 - flag[dim][k * 2];
flag[dim][k * 2 + 1] = 1 - flag[dim][k * 2 + 1];
tree[dim][k * 2] = mid - fro + 1 - tree[dim][k * 2];
tree[dim][k * 2 + 1] = to - mid - tree[dim][k * 2 + 1];
}
Xor(k * 2, fro, mid);
Xor(k * 2 + 1, mid + 1, to);
tree[dim][k] = tree[dim][k * 2] + tree[dim][k * 2 + 1];
}

int main() {

scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &num[i]);

for (dim = 0; dim <= 20; ++dim) Build(1, 1, n);

int m;
scanf("%d", &m);
while (m--) {
int way;
scanf("%d", &way);
if (way == 1) {
scanf("%d%d", &s, &e);

ll sum = 0;
for (dim = 0; dim < 20; ++dim) {
res = 0;
Sum(1, 1, n);
sum += res * (1 << dim);
}

printf("%I64d\n", sum);

} else {
scanf("%d%d%d", &s, &e, &cha);

for (dim = 0; dim < 20; ++dim)
if (cha & (1 << dim)) Xor(1, 1, n);
}
}

return 0;
}

1. 这个我早就想到了，而且我相信这也是光明会想要削减人口的原因，没什么能力的人多了会要求生存权，但是机器人明明能做得更好，于是抢走了人类赚钱的资本，不知道会不会因此爆发战争。

2. 思路二可以用一个长度为k的队列来实现，入队后判断下队尾元素的next指针是否为空，若为空，则出队指针即为所求。