zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

连续和相当于区间和,题目的意思是求所有S_i-S_j的异或和

一般位运算的题我们都拆成二进制下32位来解决

考虑每一位

枚举k

如何统计有多少个((S_i-S_j)>>k)\&1呢?

可以开两个权值树状数组来统计01的数量

如果当前S_i的第k位为1,如果S_j\&(1<<k) = 0S_i+S_j在二进制下进位不会影响到第k位的都符合条件

也就是S_j\&((1<<k)-1) \not = (S_i\&((1<<k)-1))

\&((1<<k)-1)也就是取前k

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100011,M=1000011;
int n,lim,s[N];
ll res;
struct tr{
    ll T[2*M];
    void c(int x,ll t){
        x+=1;
        for(;x<=lim+1;x+=x&(-x))T[x]+=t;
    }
    ll q(int x){
        x+=1;
        ll r=0;
        for(;x>0;x-=x&(-x))r+=T[x];
        return r;
    }
    ll s(int l,int r){return q(r)-q(l);}
    void clear(){for(int i=0;i<=lim+1;i++)T[i]=0;}
}T1,T0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        s[i]+=s[i-1];
    }
    for(int k=0;(1<<k)<=s[n];k++){
        lim=(1<<k)-1;ll ret=0;
        for(int i=0;i<=n;i++){
            int lst=s[i]&lim;
            if((s[i]>>k)&1){
                ret+=T0.s(-1,lst)+T1.s(lst,lim);
                T1.c(lst,1);
            }
            else{
                ret+=T1.s(-1,lst)+T0.s(lst,lim);
                T0.c(lst,1);
            } 
        }
        if(ret&1)res+=(1<<k);
        T1.clear();T0.clear();
    }
    printf("%lld",res);
}
LG 3760 [TJOI2017]异或和
comment评论
Search
search