这题是xor拆位法的运用
显然我们可以用t[i,j]表示第i位上的1的个数,之后求和统计(这是xor操作优化的常用手段)
zkw线段树加Lazy标记时,用tot[]表示区间上的总数(其实也可以时事算出来)
#include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<cctype> #include<iostream> using namespace std; #define MAXN (100000+10) #define MAXAi (1000000+10) #define LogMAXAi (20) #define MAXm (50000) #define NDEBUG int n,m,M,t[LogMAXAi+10][MAXN*10],tot[MAXN*10]={0}; bool b[LogMAXAi+10][MAXN*10]={0}; void build_tree() { for (int i=M+1;i<=M+n;i++) tot[i]=1; for (int i=M-1;i>=1;i--) tot[i]=tot[i<<1]+tot[(i<<1)^1]; } long long count_a_tree_node(int x) { long long ans=0; for (int i=0,p=1;i<20;i++,p<<=1) ans+=(long long)(p)*(long long)(t[i][x]); return ans; } long long quere(int l,int r) { long long ans=0; l--;r++; l+=M;r+=M; while (l^r^1) { if (~l&1) ans+=count_a_tree_node(l+1); if (r&1) ans+=count_a_tree_node(r-1); l>>=1;r>>=1; } return ans; } void pushdown(int x) { if (x!=1) pushdown(x>>1); for (int i=0;i<20;i++) { if (b[i][x]) { t[i][x<<1]=tot[x<<1]-t[i][x<<1]; t[i][(x<<1)^1]=tot[(x<<1)^1]-t[i][(x<<1)^1]; b[i][x]=0;b[i][x<<1]^=1;b[i][(x<<1)^1]^=1; } } } void update(int x) { for (int i=0;i<20;i++) { int xx=x; for (x>>=1;x;x>>=1) t[i][x]=t[i][x<<1]+t[i][(x<<1)^1]; x=xx; } } void a_t_xor(int j,int l,int r) { l--;r++; l+=M;r+=M; while (l^r^1) { if (~l&1) {t[j][l+1]=tot[l+1]-t[j][l+1];b[j][l+1]^=1; } if (r&1) {t[j][r-1]=tot[r-1]-t[j][r-1];b[j][r-1]^=1; } l>>=1;r>>=1; } } void t_xor(int l,int r,int x) { for (int i=0;x;i++,x>>=1) {if (x&1) a_t_xor(i,l,r); } } int main() { // freopen("CF_242E.in","r",stdin); memset(t,0,sizeof(t)); scanf("%d",&n); M=1;while (M-2<n) M<<=1; //cout<<M<<endl; for (int i=M+1;i<=M+n;i++) { scanf("%d",&t[0][i]); int j=0; while (t[j][i]) {t[j+1][i]=t[j][i]/2;t[j][i]&=1;j++;} } for (int j=0;j<=19;j++) { for (int i=M-1;i>=1;i--) t[j][i]=t[j][i<<1]+t[j][(i<<1)^1]; } #ifndef NDEBUG for (int i=1;i<=M+n;i++) { for (int j=0;j<=19;j++) cout<<t[j][i]<<' '; cout<<endl; } #endif build_tree(); /* for (int i=1;i<=M+n;i++) cout<<tot[i]<<' '; cout<<endl; */ scanf("%d",&m); while (m) { int p; scanf("%d",&p); if (p==1) { int l,r;scanf("%d%d",&l,&r); pushdown(l-1+M);pushdown(r+1+M); cout<<quere(l,r)<<endl; } else { int l,r,x; scanf("%d%d%d",&l,&r,&x); pushdown(l-1+M);pushdown(r+1+M); t_xor(l,r,x); update(l-1+M);update(r+1+M); } #ifndef NDEBUG for (int i=1;i<=M+n;i++) { for (int j=0;j<=19;j++) cout<<t[j][i]<<' '; cout<<endl; } #endif m--; } return 0; }