CODEFORCES DIV-841 C/ IMPORTANT QUESTION

Link- https://codeforces.com/contest/1731/problem/C

You are given an integer array a1,a2,…,an (1 ≤ ai ≤n).

Find the number of subarrays of a whose XOR has an even number of divisors. In other words, find all pairs of indices (i,j) (i≤j) such that ai⊕ai+1⊕⋯⊕aj has an even number of divisors.

For example, numbers 2, 3, 5 or 6 have an even number of divisors, while 1 and 4 — odd. Consider that 0 has an odd number of divisors in this task.

Here XOR (or ⊕) denotes the bitwise XOR operation.



Print the number of subarrays.

Input-
Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤10^4).
Description of the test cases follows.
The first line of each test case contains a single integer n (2 ≤ n ≤2⋅10^5) — the length of the array a.
The second line contains n integers a1,a2,…,an (1 ≤ ai ≤n).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output- For each test case, print the number of subarrays, whose XOR has an even number of divisors.

Example

input
4
3
3 1 2
5
4 2 1 5 3
4
4 4 4 4
7
5 7 3 7 1 7 3

output
4
11
0
20

Note
In the first test case, there are 4 subarrays whose XOR has an even number of divisors: [3], [3,1], [1,2], [2].

In the second test case, there are 11 subarrays whose XOR has an even number of divisors: [4,2], [4,2,1], [4,2,1,5], [2], [2,1], [2,1,5], [2,1,5,3], [1,5,3], [5], [5,3], [3].

In the third test case, there is no subarray whose XOR has an even number of divisors since XOR of any subarray is either 4 or 0.


/*-------------------------------------------------------------------------------------------------------------------------------------

THOUGHTS-

This problem is analogous to the problem [FIND NUMBER OF SUBARRAY WITH SUM K], the only difference here is there is no exact k, We use exclusion principle to do it. What we do here is first find the number of subarrays with XOR as square number, cuz square numbers like 0,1,4,9,16,25,.... these square numbers always have odd number of divisors. WHY? see, 1 and the number itself are divisors, but the square root of it is also a divisor and thus makes it odd count of divisors. Now, what we do is find all subarrays with square XOR, and subtract them from total number of subarrays i.e. n*(n+1)/2, giving us good subarrays. Now, how we do that, we iterate in our array one by one, and keep XORing every element, now after XORing the current element, we wanna see what XOR value can be removed from this current prefix XOR, so that the subarray becomes a square XOR. Similar to what we do in [subarray sum K], there we do sumTillNow-k to get a count of prefix sums with this values and these subarrays if subtracted from current Prefix Sum will result in a subarray with sum K. Similar we do here, but to find a XOR which we need to remove, we do this operation [xorTillNow ^ square Number] = xor to remove from prefix to get current subarray as square XOR.... This is very much analogous to [sumTillNow-k] similar to  [xorTillNow ^ square Number]. We loop over from i=0 till our i * i < 2 * n, and check if there is a prefix XOR which can be removed.

-------------------------------------------------------------------------------------------------------------------------------------*/


CODE-

-------------------------------------------------------------------------------------------------------------------------------------
USING UNORDERED HASHMAP (TLE)

#include<bits/stdc++.h>
using namespace std;

void solve(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
      cin>>arr[i];
  }
  long long int res=0;
  unordered_map<long long int,int> mpp;
  long long int currXOR=0;
  for(int i=0;i<n;i++){
      currXOR=currXOR ^ arr[i];
      for(int j=0;j*j<2*n;j++){
          long long int sq=j*j;
          if(currXOR==sq){
              res++;
          }
          if(mpp.find(currXOR ^ sq)!=mpp.end() && (currXOR ^ sq) < 2 * n ){
              res+=mpp[currXOR ^ sq];
          }
      }
      mpp[currXOR]++;
  }
  cout<<((long long int)n*(n+1)/2)-res<<endl;
}

int main(){
    int TC;
    cin>>TC;
    while(TC--){
      solve();
    }
}
-------------------------------------------------------------------------------------------------------------------------------------

USING FREQ ARRAY INSTEAD OF HASHMAP  (ACCEPTED)

#include<bits/stdc++.h>
using namespace std;

void solve(){
  int n;
  cin>>n;
  int arr[n];
  for(int i=0;i<n;i++){
      cin>>arr[i];
  }
  long long int res=0;
  vector<long long int> freq(2*n,0);
  long long int currXOR=0;
  for(int i=0;i<n;i++){
      currXOR=currXOR ^ arr[i];
      for(int j=0;j*j<2*n;j++){  // as per your constraint, your element will never be greater than 2 * n.
          long long int sq=j*j;
          if(sq==currXOR){
              res++;
          }
          if((currXOR ^ sq) < 2 * n){ // as per your constraint, your element will never be greater than 2 * n.
              res+=freq[currXOR ^ sq];
          }
      }
      freq[currXOR]++;
  }
  cout<<((long long int)n*(n+1)/2)-res<<endl;
}

int main(){
    int TC;
    cin>>TC;
    while(TC--){
      solve();
    }
}