fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 3e5+10,mod = 1e9+7;
  5. ll s[N];
  6. ll a[N];
  7. ll l[N][2],r[N][2];
  8. int check(int x)
  9. {
  10.      for(int i=30;i>=0;i--)
  11.      {
  12.           if((x>>i)&1) return i;
  13.      }
  14. }
  15. void slove()
  16. {
  17.     ll sum=0;
  18.     int n;
  19.     cin>>n;
  20.     for(int i=1;i<=n;i++)
  21.     {
  22.         cin>>a[i];
  23.         s[i]=s[i-1]^a[i];
  24.     }
  25.     for(int i=0;i<=30;i++)
  26.     {
  27.         l[i][1]=l[i][0]=0;
  28.         r[i][1]=r[i][0]=0;
  29.     }
  30.     for(int i=1;i<=n;i++)
  31.     {
  32.         for(int j=0;j<=30;j++)
  33.         {
  34.             l[j][0]=1;
  35.             if((s[i]>>j)&1) r[j][1]++;
  36.             else r[j][0]++;
  37.         }
  38.     }
  39.  
  40.     for(int i=1;i<=n;i++)
  41.     {
  42.         int x=check(a[i]);
  43.         sum+=l[x][1]*r[x][1];
  44.         sum+=l[x][0]*r[x][0];
  45.  
  46.         cout << x << "\n";
  47.         cout << l[x][0] << " " << l[x][1] << " " << r[x][0] << " " << r[x][1] << "\n";
  48.         for(int j=0;j<=30;j++)
  49.         {
  50.             if((s[i]>>j)&1) r[j][1]--;
  51.             else r[j][0]--;
  52.         }
  53.         for(int j=0;j<=30;j++)
  54.         {
  55.             if((s[i]>>j)&1) l[j][1]++;
  56.             else l[j][0]++;
  57.         }
  58.     }
  59.     cout<<sum<<"\n";
  60. }
  61. int main()
  62. {
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     cout.tie(nullptr);
  66.     int t=1;
  67.     cin>>t;
  68.     while(t--)
  69.     slove();
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 9564KB
comments (?)
stdin
copy 
1
5
7 3 7 2 1
stdout
copy 
2
1 0 3 2
1
1 1 3 1
2
1 2 3 0
1
2 2 2 0
0
2 3 1 0
16
https://ideone.com/kAqNWl
language:
C++14 (clang 8.0)
created:
11 days 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!