http://codeforces.com/problemset/problem/242/E
题意：给出初始n个数，还有m个操作，操作一种是区间求和，一种是区间xor x。
思路：昨天比赛出的一道类似题目，对于一个数，把它变成二进制，那么做xor操作的时候，其实如果那一位xor 1，那么就是取反，否则不变。于是，可以对每一个二进制位开一棵线段树，由于数字最大有1e6，所以只需要开log(1e6) = 20棵线段树。对每一棵线段树统计区间内1的个数，那一位对答案的贡献就是那一位的权值*区间1的个数。在作xor操作的时候，如果是xor的数1，那么就是区间内所有的1变成0，0变成1，这一段的和就变成（长度 - 原本的值），否则不变。
pushdown操作对右子树操作少了一个|1，导致调试好久，一定要细心！
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long LL;
#define N 100010
#define INF 0x3f3f3f3f
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r
int tree[][N<<], lazy[][N<<], bit[];
LL weight[]; void pushup(int id, int rt) { tree[id][rt] = tree[id][rt<<] + tree[id][rt<<|]; } void pushdown(int id, int rt, int len, int l, int r) {
if(lazy[id][rt]) {
tree[id][rt<<] = (len - len / ) - tree[id][rt<<];
tree[id][rt<<|] = (len / ) - tree[id][rt<<|];
lazy[id][rt<<] ^= ; lazy[id][rt<<|] ^= ;
lazy[id][rt] = ;
}
} void update(int id, int rt, int l, int r, int L, int R, int w) {
if(L <= l && r <= R) {
if(w) tree[id][rt] = (r - l + - tree[id][rt]);
lazy[id][rt] ^= w;
return ;
}
pushdown(id, rt, r - l + , l, r);
int m = (l + r) >> ;
if(L <= m) update(id, lson, L, R, w);
if(m < R) update(id, rson, L, R, w);
pushup(id, rt);
} int query(int id, int rt, int l, int r, int L, int R) {
if(L <= l && r <= R) return tree[id][rt];
pushdown(id, rt, r - l + , l, r);
int m = (l + r) >> ;
int ans = ;
if(L <= m) ans += query(id, lson, L, R);
if(m < R) ans += query(id, rson, L, R);
return ans;
} int main()
{
int n, num, q, maxn = ;
scanf("%d", &n);
for(int i = ; i <= ; i++) weight[i] = 1LL << (i - );
for(int i = ; i <= n; i++) {
scanf("%d", &num);
int tmp = num, cnt = ;
while(tmp) {
bit[++cnt] = tmp & ;
tmp >>= ;
}
if(cnt > maxn) maxn = cnt;
for(int j = cnt; j >= ; j--) update(j, , , n, i, i, bit[j]);
}
scanf("%d", &q);
while(q--) {
int type, l, r, w;
scanf("%d%d%d", &type, &l, &r);
if(type == ) {
LL ans = ;
for(int i = ; i <= maxn; i++) {
int num = query(i, , , n, l, r);
ans += weight[i] * num;
}
printf("%I64d\n", ans);
} else {
scanf("%d", &w);
int cnt = ;
while(w) {
bit[++cnt] = w & ;
w >>= ;
}
if(cnt > maxn) maxn = cnt;
for(int j = cnt; j >= ; j--) update(j, , , n, l, r, bit[j]);
}
}
return ;
}