fork download
copy 
  1.  
  2. /// TRIE…….XOR SUM(LESS THAN K)……
  3.  
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define ll long long
  7. #define maxn 5000050
  8.  
  9. bool check(ll n,ll pos)
  10. {
  11.     return (bool)(n&(1LL<<pos));
  12. }
  13.  
  14.  
  15. ll cumxor[100005];
  16. ll n;
  17.  
  18.  
  19. struct Trie
  20. {
  21.     ll nextt[maxn][2];
  22.     ll traverse[maxn];
  23.     ll sz;
  24.     Trie()
  25.     {
  26.         clear();
  27.     }
  28.     void clear()
  29.     {
  30.         sz=0;
  31.         memset(nextt[0],-1,sizeof(nextt[0]));
  32.         memset(traverse,0,sizeof traverse);
  33.     }
  34.     void add(ll val)
  35.     {
  36.         ll v=0;
  37.         for(ll i = 32; i>= 0; --i)
  38.         {
  39.             int id = check(val,i);
  40.             if(nextt[v][id] == -1)
  41.             {
  42.                 nextt[v][id]=++sz;
  43.                 memset(nextt[sz],-1,sizeof(nextt[sz]));
  44.             }
  45.             v=nextt[v][id];
  46.             traverse[v]++;
  47.         }
  48.     }
  49.     ll dfs(ll val,ll k)
  50.     {
  51.         ll v=0;
  52.         ll ans=0;
  53.         for(ll i=32; i>=0 ; i--)
  54.         {
  55.             ll id=check(val,i);
  56.             ll kid=check(k,i);
  57.             if(kid==1){
  58.                 ans+=traverse[nextt[v][id]];
  59.                 v=nextt[v][id^1];
  60.             }
  61.             else
  62.                 v=nextt[v][id];
  63.             if(v==-1)
  64.                 break;
  65.         }
  66.         return ans;
  67.     }
  68. };
  69.  
  70. Trie tree;
  71. vector<ll>as;
  72.  
  73. int main()
  74. {
  75.     ll tes,k;
  76.     scanf("%lld",&tes);
  77.     for(ll cas=1;cas<=tes;cas++)
  78.     {
  79.           tree.clear();
  80.           scanf("%lld%lld",&n,&k);
  81.           tree.add(0);
  82.           ll ans=0;
  83.           for(ll i=1;i<=n;i++)
  84.           {
  85.               scanf("%lld",&cumxor[i]);
  86.               cumxor[i]=cumxor[i-1]^cumxor[i];
  87.               ans+=tree.dfs(cumxor[i],k);
  88.               tree.add(cumxor[i]);
  89.           }
  90.           printf("%lld\n",ans);
  91.     }
  92.     return 0;
  93. }
  94.  
Success #stdin #stdout 0.03s 42692KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
https://ideone.com/NFLY8t
language:
C++14 (gcc 8.3)
created:
3 years 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!