fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std ;
  3. const int N=3e5+5;
  4. const int M=1e6+5;
  5. int arr[N]; // storing the input;
  6. int pos[M];// it stores the index of last occurence of i(number);
  7. int countt[N];// it denotes the number of distinct elements in the array from 0 to i(0 based indexing);
  8. int node[4*N+5];// segment tree;
  9. int sum(int i , int j , int  l , int r ,int index)
  10. {
  11. 	if(j<l||i>r)
  12. 	{
  13. 	return 0;
  14. 	}
  15. 	if(i>=l&&j<=r)
  16. 	{
  17. 	return node[index];
  18. 	}
  19. 	int mid=(i+j)/2;
  20. 	int left=sum(i,mid,l,r,2*index);
  21. 	int right=sum(mid+1,j,l,r,2*index+1);
  22. 	node[index]=left+right;
  23. 	return node[index];
  24. }
  25. void build(int i, int j , int index)
  26. {
  27. 	if(i==j)
  28. 	{
  29. 		node[index]=countt[i];
  30. 		return ;
  31. 	}
  32. 	int mid=(i+j)/2;
  33. 	build(i,mid,2*index);
  34. 	build(mid+1,j,2*index+1);
  35. 	node[index]=node[2*index]+node[2*index+1];
  36. 	return;
  37. }
  38. int main ()
  39. {
  40. 	int n;
  41. 	cin >> n ;
  42. 	memset(pos,-1,sizeof(pos));// it is denoting that for all are input values, the index of previous occurence of them is not yet calculated.
  43. 	memset(node,0,sizeof(node));
  44. 	memset(countt,0,sizeof(countt));
  45. 	for (int i=0;i<n;i++)
  46. 	{
  47. 		cin >> arr[i];
  48. 	}
  49. 	// Taking in queries
  50. 	int m ;
  51. 	cin >> m;
  52. 	vector<int>v[n+1];// for storing the queries ending with r ;
  53. 	map<pair<int,int>,int>mp;//Just for having a track of queries;
  54. 	for (int i=0;i<m;i++)
  55. 	{
  56. 		int l , r ;
  57. 		cin >> l >> r;
  58. 		l--,r--;
  59. 		v[r].push_back(l);
  60. 		pair<int,int>temp=make_pair(l,r);
  61. 		mp[temp]=i;
  62. 	}
  63. 	// a query is denoted by (l,r)
  64. 	// Now we are treating each i as r of a query;
  65. 	int s[m+5];
  66. 	for (int i=0;i<n;i++)
  67. 	{
  68. 		if(pos[arr[i]]!=-1)// This means that if there is any previous occurence of arr[i] till ith index,we need to remove that in order to calculate
  69. 		{					// distinct elements that is why we have stored the index of that previous occurence in pos[arr[i] , now for that position
  70. 			countt[pos[arr[i]]]--;// we will decrement its countt[pos[arr[i]];
  71. 		}
  72. 		pos[arr[i]]=i;// Now once we have removed that previous occurence of arr[i], now we also need to include it again as is in the range till i(for which we are
  73. 		countt[pos[arr[i]]]++;// calculating for now) , hence our new position of arr[i] will become i only;
  74. 		//Now for all queries ending with i(as their r), we need to calculate our sum from l to r for which we can use segment tree;
  75. 		if(v[i].size()!=0)
  76. 		build(0,n-1,1);
  77. 		for (int q=0;q<v[i].size();q++)
  78. 		{
  79. 			long long ans=sum(0,n-1,v[i][q],i,1);
  80. 			pair<int,int>t=make_pair(v[i][q],i);
  81. 			s[mp[t]]=ans;
  82. 		}
  83. 	}
  84. 	for (int i=0;i<m;i++)
  85. 	cout<<s[i]<<"\n";
  86. }
Success #stdin #stdout 0.01s 13292KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/Uc7OYv
problem DQUERY, based on SPOJ submission 28225084 (CPP14), 2021-07-20 22:01:21
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!