fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7. 	int t;
  8.  
  9. 	cin >> t ;
  10.  
  11. 	while(t--)
  12. 	{
  13. 		int n;
  14.  
  15. 		scanf("%d", &n);
  16.  
  17. 		int a[n];
  18.  
  19. 		for(int i = 0; i < n; i++)
  20. 		{
  21. 			scanf("%d", &a[i]);
  22. 		}
  23.  
  24. 		map<int, pair<int, int> > mp;
  25.  
  26. 		long long int XOR[100007], ans[100007];
  27.  
  28. 		mp[0].first = -1;
  29. 		mp[0].second = 1;
  30.  
  31. 		for(int i = 0; i < n; i++)
  32. 		{
  33. 			if(i == 0)
  34. 				XOR[i] = a[i];
  35. 			else XOR[i] = XOR[i - 1] ^ a[i];
  36.  
  37. 			int temp = XOR[i];
  38.  
  39. 			if(mp.find(temp) == mp.end())
  40. 			{
  41. 				ans[i] = 0;
  42.  
  43. 				mp[temp].first = i;
  44. 				mp[temp].second = 1;
  45. 			}
  46. 			else
  47. 			{
  48. 				int ind = mp[temp].first, freq = mp[temp].second;
  49.  
  50.                 if(temp == 0 && ind == -1)
  51.                     ans[i] = i;
  52.                 else if(ind == 0)
  53.                     ans[i] = ans[ind] + freq * (i - ind - 1);
  54.                 else
  55. 				    ans[i] = ans[ind] + freq * (i - ind - 1) + (freq - 1);
  56.  
  57. 				mp[temp].first = i;
  58. 				mp[temp].second = freq + 1;
  59. 			}
  60. 		}
  61.  
  62. 		long long int final = 0;
  63.  
  64.         // for(int i = 0; i < n; i++)
  65.         //     cout << ans[i] << " ";
  66.         // cout << "\n";
  67.  
  68. 		for(int i = 0; i < n; i++)
  69. 		{
  70. 			final += ans[i];
  71. 		}
  72.  
  73. 		printf("%lld\n", final);
  74. 	}
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 4396KB
comments (?)
stdin
copy 
1
5
1 1 1 1 1
stdout
copy 
10
https://ideone.com/T5EZpr
language:
C++14 (gcc 8.3)
created:
4 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!