fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5. #define MAX 30009
  6. #define mii map<int,int>
  7. int arr[MAX];
  8. mii tree[MAX<<2];
  9. mii::iterator itr;
  10.  
  11. void merge(mii &t,mii a,mii &b)
  12. {
  13. 	t=a;
  14. 	for(itr=b.begin();itr!=b.end();itr++)
  15. 		t[itr->first]++;
  16. }
  17.  
  18. void build(int t,int i,int j)
  19. {
  20. 	if(i==j){
  21. 		tree[t][arr[i]]++;
  22. 		return;
  23. 	}
  24. 	int l=t<<1,r=l+1,mid=(i+j)>>1;
  25. 	build(l,i,mid);
  26. 	build(r,mid+1,j);
  27. 	merge(tree[t],tree[l],tree[r]);
  28. }
  29.  
  30. mii query(int t,int i,int j,int ri,int rj)
  31. {
  32. 	mii tmp,a,b;
  33. 	if(j<ri||i>rj)
  34. 		return a;
  35.  
  36. 	if(ri<=i && rj>=j)
  37. 		return tree[t];
  38.  
  39. 	int l=t<<1,r=l+1,mid=(i+j)>>1;
  40. 	a = query(l,i,mid,ri,mid);
  41. 	b = query(r,mid+1,j,mid+1,rj);
  42. 	merge(tmp,a,b);
  43. 	return tmp;
  44. }
  45.  
  46. int main() {
  47. 	int n,q,a,b;
  48. 	mii t;
  49. 	cin>>n;
  50. 	for(int i=1;i<=n;i++)
  51. 		cin>>arr[i];
  52. 	build(1,1,n);
  53. 	cin>>q;
  54. 	while(q--)
  55. 	{
  56. 		cin>>a>>b;
  57. 		t = query(1,1,n,a,b);
  58. 		cout<<t.size()<<endl;
  59. 	}
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 5756KB
comments (?)
stdin
copy 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout
copy 
3
2
3
https://ideone.com/1CcC8d
http://w...content-available-to-author-only...j.com/problems/DQUERY/en/
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!