fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lld;
  4. const int MAXN = 3e4 + 5;
  5. const int MAXM = 2e5 + 5;
  6. const int MAXS = 1e6 + 5;
  7. const int SZ = 200;
  8.  
  9. struct Q{
  10. 	int x, y, id;
  11. 	Q(int _x = 0, int _y = 0, int _id = 0): x(_x), y(_y), id(_id) {}
  12.  
  13. 	bool operator < (const Q &rhs) const
  14. 	{
  15. 		return y < rhs.y;
  16. 	}
  17. };
  18. int n,m;
  19.  
  20. vector< vector<Q> > bckt;
  21. int a[MAXN];
  22. int ans[MAXM];
  23. int cnt[MAXS];
  24.  
  25. int main()
  26. {
  27. 	scanf("%d", &n);
  28. 	for(int i = 0; i < n; ++i){
  29. 		scanf("%d", &a[i]);
  30. 	}
  31.  
  32. 	bckt = vector< vector<Q> >(n / SZ + 1);
  33.  
  34. 	scanf("%d", &m);
  35. 	for(int i = 0; i < m; ++i){
  36. 		int x, y;
  37. 		scanf("%d%d", &x, &y);
  38. 		x--; y--;
  39. 		bckt[x / SZ].push_back(Q(x, y, i));
  40. 	}
  41. 	for(auto& c: bckt) sort(c.begin(), c.end());
  42.  
  43. 	for(int i = 0; i < bckt.size(); ++i){
  44. 		int l = i * SZ;
  45. 		int r = l - 1;
  46. 		int cur = 0;
  47. 		for(auto &q: bckt[i]){
  48. 			while(r < q.y){
  49. 				++r;
  50. 				cnt[a[r]]++;
  51. 				if(cnt[a[r]] == 1){
  52. 					++cur;
  53. 				}
  54. 			}
  55. 			while(l < q.x){
  56. 				cnt[a[l]]--;
  57. 				if(cnt[a[l]] == 0){
  58. 					--cur;
  59. 				}
  60. 				++l;
  61. 			}
  62. 			while(l > q.x){
  63. 				--l;
  64. 				cnt[a[l]]++;
  65. 				if(cnt[a[l]] == 1){
  66. 					++cur;
  67. 				}
  68. 			}
  69. 			ans[q.id] = cur;
  70. 		}
  71. 		while(l <= r){
  72. 			cnt[a[l]]--;
  73. 			if(cnt[a[l]] == 0){
  74. 				--cur;
  75. 			}
  76. 			++l;
  77. 		}
  78. 	}
  79.  
  80. 	for(int i = 0; i < m; ++i){
  81. 		printf("%d\n", ans[i]);
  82. 	}
  83. }
Success #stdin #stdout 0s 8264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OLG0dB
problem : http://w...content-available-to-author-only...j.com/problems/DQUERY/
language:
C++14 (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!