给n个数， 两种操作， 一种是求区间内的数的和， 一种是将区间内的数异或x。
异或x没有什么思路， 单个异或肯定超时， 区间异或也没有办法做....后来才知道可以按位建线段树， 这样建20棵线段树就可以。
每一次异或， 对于给定的x， 如果x的第i位是1， 那么就将第i棵线段树在给定的区间内0，1翻转， 这是很基础的操作。
对于区间求和操作， 我们可以求出给定的区间， 从高位到低位， 每一位依次有多少个1， 然后就可以直接求出来， 感觉不好表达....具体看代码。
#include<bits/stdc++.h>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ull unsigned long long
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 1e5+;
int sum[maxn<<][], XOR[maxn<<][], a[];
void pushUp(int rt, int pos) {
sum[rt][pos] = sum[rt<<][pos] + sum[rt<<|][pos];
}
void pushDown(int rt, int m, int pos) {
if(XOR[rt][pos]) {
sum[rt<<][pos] = (m-(m>>)) - sum[rt<<][pos];
sum[rt<<|][pos] = (m>>)-sum[rt<<|][pos];
XOR[rt<<][pos] ^= ;
XOR[rt<<|][pos] ^= ;
XOR[rt][pos] = ;
}
}
void update(int L, int R, int l, int r, int rt, int pos) {
if(L<=l&&R>=r) {
XOR[rt][pos] ^= ;
sum[rt][pos] = r-l+-sum[rt][pos];
return ;
}
pushDown(rt, r-l+, pos);
int m = l+r>>;
if(L<=m)
update(L, R, lson, pos);
if(R>m)
update(L, R, rson, pos);
pushUp(rt, pos);
}
int query(int L, int R, int l, int r, int rt, int pos) {
if(L<=l&&R>=r) {
return sum[rt][pos];
}
pushDown(rt, r-l+, pos);
int m = l+r>>, ret = ;
if(L<=m)
ret += query(L, R, lson, pos);
if(R>m)
ret += query(L, R, rson, pos);
return ret;
}
int main()
{
int n, x, m, y, sign, z;
cin>>n;
mem(XOR);
for(int i = ; i<=n; i++) {
scanf("%d", &x);
for(int j = ; j<; j++) {
if((<<j)&x) {
update(i, i, , n, , j);
}
}
}
cin>>m;
while(m--) {
scanf("%d", &sign);
if(sign==) {
ll tmp = ;
scanf("%d%d", &x, &y);
for(int i = ; i>=; i--) {
tmp = 1ll*tmp*+query(x, y, , n, , i); //query是求这个区间里每一位有多少个1
}
cout<<tmp<<endl;
} else {
scanf("%d%d%d", &x, &y, &z);
for(int j = ; j<; j++) {
if(z&(<<j)) { //如果给出的x第j位是1， 那么就将区间内第j棵线段树翻转
update(x, y, , n, , j);
}
}
}
}
return ;
}