fork download
copy 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. #include<string.h>	//for memset
  4. #include<vector>
  5. using namespace std;
  6. #define MAX 30009
  7. struct input
  8. {
  9. 	int s,e,val,p;	//p for position, -1 for update, value for query position
  10. };
  11. int lastpos[1000009];	//To store previous occurance of the integer
  12. int bit[MAX];		//Stores count of distinct integers in a given range
  13.  
  14. void update(int val,int pos)
  15. {
  16. 	while(pos<MAX)
  17. 	{
  18. 		bit[pos]+=val;
  19. 		pos=pos+(pos&-pos);
  20. 	}
  21. }
  22. int query(int pos)
  23. {
  24. 	int sum=0;
  25. 	while(pos>0)
  26. 	{
  27. 		sum+=bit[pos];
  28. 		pos=pos-(pos&-pos);
  29. 	}
  30. 	return sum;
  31. }
  32. int cmp(struct input f,struct input s)
  33. {
  34. 	if(f.e<s.e)
  35. 		return 1;
  36. 	if(f.e>s.e)
  37. 		return 0;
  38. 	if(f.s<=s.s)
  39. 		return 1;
  40. 	return 0;
  41. }
  42. int main()
  43. {
  44. 	int n,ip,q,a,b;
  45. 	memset(bit,0,sizeof(bit));
  46. 	memset(lastpos,0,sizeof(lastpos));
  47. 	vector <struct input> abc;
  48. 	scanf("%d",&n);
  49. 	for(int i=0;i<n;i++)		//stores the array	
  50. 	{
  51. 		scanf("%d",&ip);
  52. 		struct input temp;
  53. 		temp.s=temp.e=i+1;	//start and end point equal, i+1 as 1 based indexing
  54. 		temp.val=ip;		//value at the array position
  55. 		temp.p=-1;		//-1 means update operation
  56. 		abc.push_back(temp);
  57. 	}
  58. 	scanf("%d",&q);
  59. 	int ans[q];	//stores answer for each query
  60. 	memset(ans,0,sizeof(ans));
  61. 	for(int i=0;i<q;i++)
  62. 	{
  63. 		struct input temp;
  64. 		scanf("%d%d",&a,&b);	//query range
  65. 		temp.s=a;
  66. 		temp.e=b;
  67. 		temp.val=0;		//Value of range is not required, any random value should work
  68. 		temp.p=i;		//query number
  69. 		abc.push_back(temp);
  70. 	}
  71. 	sort(abc.begin(),abc.end(),cmp);
  72.  
  73. //	for(int i=0;i<abc.size();i++)
  74. //	{
  75. //		printf("start = %d \t end = %d\n",abc[i].s,abc[i].e);
  76. //	}
  77. 	for(int i=0;i<abc.size();i++)
  78. 	{
  79. 		if(abc[i].p!=-1)	//query
  80. 		{
  81. 			int t=query(abc[i].e)-query(abc[i].s-1);
  82. 			ans[abc[i].p]=t;
  83. 		}
  84. 		else
  85. 		{
  86. 			if(lastpos[abc[i].val]==0)	//means not occured, as we are using 1 based indexing
  87. 			{
  88. 				lastpos[abc[i].val]=abc[i].s;	//last occuring position is the present position
  89. 				update(1,lastpos[abc[i].val]);	//add 1 to the last occuring position
  90. 			}
  91. 			else
  92. 			{
  93. 				update(-1,lastpos[abc[i].val]);	//remove the previous last occured position
  94. 				lastpos[abc[i].val]=abc[i].s;	//last occuring position is the present position
  95. 				update(1,lastpos[abc[i].val]);	//add 1 to the last occuring position
  96. 			}
  97. 		}
  98. 	}
  99. 	for(int i=0;i<q;i++)
  100. 		printf("%d\n",ans[i]);
  101. }
Success #stdin #stdout 0s 7484KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
2
2
2
https://ideone.com/63xUKl
language:
C++ (gcc 8.3)
created:
8 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!