BZOJ4017 小Q的无敌异或好题-白红宇

BZOJ4017 小Q的无敌异或好题

阅读量：4697 次

发布时间：2019-06-09

本文共 1434 字，大约阅读时间需要 4 分钟。

给一个序列

询问这个序列

1：所有子区间的异或值的和

2：所有子区间的和的异或值

第一个操作，拆二进制位，枚举右端点r，记录这个位前r个数字0/1的个数，右端点转移O(1)

第二个操作比较复杂，对于每个右端点要询问sum[r]-sum[l-1]mod(2^(k+1))>=2^k的左端点个数（的奇偶性）

题解用了树状数组维护，参考，题解里对于模不等式的解释很巧妙，复习的时候多看看吧

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                using namespace std;#define ll long long#define ull unsigned long long#define pb push_back#define mem(a) memset(a,0,sizeof a)#define FOR(a) for(int i=1;i<=a;i++) const int inf =0x3f3f3f3f; const int maxn=1e5+7;const int mod=998244353;int n;int a[maxn],x[maxn],bit[maxn],ans1;ll s[maxn],p[maxn],ans2;void inc(int &x,int y){ x+=y;if(x>=mod)x-=mod;}void add(int x){ for(;x<=n;x+=~x&x+1) bit[x]^=1;}int sum(int x){ int ret=0; for(;x>=0;x-=~x&x+1) ret^=bit[x]; return ret;}int idx(ll val){ //return lower_bound(p,p+n,val)-p; int L=-1,R=n; while(L
                
                 >1; if(p[M]<=val)L=M; else R=M-1; } return L; }int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); x[i]=x[i-1]^a[i]; s[i]=s[i-1]+a[i]; } //异或的和 for(int k=0,powk=1;k<30;++k,inc(powk,powk)){ //枚举指数 int cnt[2]={},tmp=0; for(int i=0;i<=n;i++){ inc(tmp,cnt[((x[i]>>k)&1)^1]); ++cnt[(x[i]>>k)&1]; } inc(ans1,1ll*powk*tmp%mod); } //和的异或 for(int k=0;(1ll<
                 
                  <=s[n];++k){ int tmp=0; for(int i=0;i<=n;i++){ p[i]=s[i]&((1ll<