fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Trie {
  5.     Trie* child[2]{nullptr,nullptr};
  6.     long long cnt=0;
  7. };
  8.  
  9. void insert(Trie* root,int num,long long val){
  10.     Trie* node=root;
  11.     for(int i=30;i>=0;i--){
  12.         int b=(num>>i)&1;
  13.         if(!node->child[b]) node->child[b]=new Trie();
  14.         node=node->child[b];
  15.         node->cnt+=val;
  16.     }
  17. }
  18.  
  19. long long query(Trie* node,int num,int limit,int bit=30){
  20.     if(!node) return 0;
  21.     if(bit<0) return node->cnt;
  22.     int bnum=(num>>bit)&1;
  23.     int blim=(limit>>bit)&1;
  24.     if(blim){
  25.         long long res=0;
  26.         if(node->child[bnum]) res+=node->child[bnum]->cnt;
  27.         res+=query(node->child[bnum^1],num,limit,bit-1);
  28.         return res;
  29.     } else {
  30.         return query(node->child[bnum],num,limit,bit-1);
  31.     }
  32. }
  33.  
  34. int main(){
  35.     ios::sync_with_stdio(false);
  36.     cin.tie(0);
  37.     int n,k;
  38.     cin>>n>>k;
  39.     vector<int> a(n+1),l(k+1),r(k+1);
  40.     for(int i=1;i<=n;i++) cin>>a[i];
  41.     for(int i=1;i<=k;i++) cin>>l[i]>>r[i];
  42.     vector<int> pxor(n+1);
  43.     for(int i=1;i<=n;i++) pxor[i]=pxor[i-1]^a[i];
  44.     vector<map<int,long long>> dp(k+1);
  45.     dp[0][0]=1;
  46.     for(int s=1;s<=k;s++){
  47.         Trie* root=new Trie();
  48.         for(auto [val,cnt]: dp[s-1]) insert(root,val,cnt);
  49.         for(int i=1;i<=n;i++){
  50.             long long res=query(root,pxor[i],r[s])-query(root,pxor[i],l[s]-1);
  51.             if(res) dp[s][pxor[i]]+=res;
  52.         }
  53.     }
  54.     long long ans=0;
  55.     for(auto [x,v]: dp[k]) ans+=v;
  56.     cout<<ans<<"\n";
  57. }
  58.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin 
4 2
1 2 3 4
1 4
2 10
stdout 
8
https://ideone.com/YfxxJp
language:
C++14 (clang 8.0)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!