fork download
copy 
  1. #include<iostream>
  2. #include<map>
  3. #include<cmath>
  4. #include<cstring>
  5. using namespace std;
  6. int a[100005];
  7. int main()
  8. {
  9. 	int ty,i,x,s,e,count,ans,k,blk,p;
  10. 	int n,q;
  11. 	scanf("%d%d",&n,&q);
  12. 	for(int i=0;i<n;i++)
  13. 		scanf("%d",&a[i]);
  14. 	int BLOCK_SIZE=(int)ceil(sqrt(n));
  15. 	int BLOCKS=(int)ceil(sqrt(n));
  16. 	int b[BLOCKS];
  17. 	memset(b,0,sizeof(b));
  18. 	for(int i=0;i<n;i++)
  19. 		b[i/BLOCK_SIZE]^=a[i];
  20. 	map<int,int> m1[BLOCKS];
  21. 	for(int i=0;i<BLOCKS;i++)
  22. 	{
  23. 		s=i*BLOCK_SIZE;
  24. 		e=(i+1)*BLOCK_SIZE-1;
  25. 		map<int,int> m;
  26. 		x=0;
  27. 		for(int j=s;j<=e;j++)
  28. 		{
  29. 			x^=a[j];
  30. 			m[x]++;
  31. 		}
  32. 		m1[i]=m;
  33. 	}
  34.  
  35. 	while(q--)
  36. 	{
  37. 		scanf("%d",&ty);
  38. 		if(ty==1)
  39. 		{
  40. 			scanf("%d%d",&i,&x);
  41. 			i--;
  42. 			blk=i/BLOCK_SIZE;
  43. 			s=blk*BLOCK_SIZE;
  44. 			e=(blk+1)*BLOCK_SIZE-1;
  45. 			a[i]=x;
  46. 			b[blk]=0;
  47. 			for(int i=s;i<=e;i++)
  48. 				b[blk]^=a[i];
  49. 			map<int,int> m;
  50. 			ans=0;
  51. 			for(int i=s;i<=e;i++)
  52. 			{
  53. 				ans^=a[i];
  54. 				m[ans]++;
  55. 			}
  56. 			m1[blk]=m;
  57. 		}
  58. 		else
  59. 		{	
  60. 			scanf("%d%d",&i,&k);
  61. 			i--;
  62. 			count=0;
  63. 			ans=0;
  64. 			if(i<BLOCK_SIZE)
  65. 			{
  66. 				for(int j=0;j<=i;j++)
  67. 				{
  68. 					ans^=a[j];
  69. 					if(ans==k)
  70. 						count++;
  71. 				}
  72. 			}
  73. 			else
  74. 			{
  75. 				blk=i/BLOCK_SIZE;
  76. 				for(int j=0;j<=blk-1;j++)
  77. 				{
  78. 					p=ans^k;
  79. 					count+=m1[j].count(p);
  80. 					ans^=b[j];
  81. 				}
  82. 				s=blk*BLOCK_SIZE;
  83. 				e=i;
  84. 				p=0;
  85. 				for(int j=s;j<=e;j++)				
  86. 				{
  87. 					p^=a[j];
  88. 					if((ans^p)==k)
  89. 						count++;					
  90. 				}
  91. 			}
  92. 			printf("%d\n",count);
  93. 		}
  94. 	}
  95.  
  96. 	return 0;
  97. }
  98.  
Time limit exceeded #stdin #stdout 5s 4308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZRcgp0
language:
C++ (gcc 8.3)
created:
6 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!