fork(6) download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <set>
  6. #include <tuple>
  7. #include <unordered_set>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. const int MAXA = 100000;
  13. const int MAXN = 100000;
  14. const int MAXQ = 100000;
  15.  
  16. int a[MAXN];
  17. typedef tuple<int, int, int, int> Query;
  18. Query query[MAXQ];
  19.  
  20. inline void moAlgorithm(const int n, const int a[], const int q, tuple<int, int, int, int> query[])
  21. {
  22. 	const int blockSize = (int)sqrt((long double)n);
  23.  
  24. 	const auto getLeft = [](const Query &q) {return get<0>(q); };
  25. 	const auto getRight = [](const Query &q) {return get<1>(q); };
  26. 	const auto getBlockIndex = [=](const Query &q) {return getLeft(q) / blockSize; };
  27.  
  28. 	sort(query, query + q, [=](const Query &a, const Query &b) {
  29. 		return
  30. 			getBlockIndex(a) < getBlockIndex(b) ||
  31. 			getBlockIndex(a) == getBlockIndex(b) && getRight(a) > getRight(b);
  32. 	});
  33.  
  34. 	static int count[MAXA + 1];
  35. 	memset(count, 0, sizeof(count));
  36. 	static int numberOfValuesWithCount[MAXN + 1];
  37. 	memset(numberOfValuesWithCount, 0, sizeof(*numberOfValuesWithCount) * (n + 1));
  38. 	int maxCount = 0;
  39.  
  40. 	const auto remove = [&](const int index) {
  41. 		--numberOfValuesWithCount[count[a[index]]];
  42. 		if (count[a[index]] == maxCount && numberOfValuesWithCount[count[a[index]]] == 0)
  43. 		{
  44. 			--maxCount;
  45. 		}
  46. 		--count[a[index]];
  47. 		++numberOfValuesWithCount[count[a[index]]];
  48.  
  49. 	};
  50. 	const auto add = [&](const int index) {
  51. 		--numberOfValuesWithCount[count[a[index]]];
  52. 		if (count[a[index]] == maxCount)
  53. 		{
  54. 			++maxCount;
  55. 		}
  56. 		++count[a[index]];
  57. 		++numberOfValuesWithCount[count[a[index]]];
  58. 	};
  59.  
  60. 	int left = 0, right = -1;
  61.  
  62. 	for (int i = 0; i < q; ++i)
  63. 	{
  64. 		for (; left < getLeft(query[i]); ++left)
  65. 		{
  66. 			remove(left);
  67. 		}
  68. 		for (; left > getLeft(query[i]); )
  69. 		{
  70. 			add(--left);
  71. 		}
  72. 		for (; right < getRight(query[i]); )
  73. 		{
  74. 			add(++right);
  75. 		}
  76. 		for (; right > getRight(query[i]); --right)
  77. 		{
  78. 			remove(right);
  79. 		}
  80. 		get<3>(query[i]) = maxCount;
  81. 	}
  82.  
  83. 	sort(query, query + q, [=](const Query &a, const Query &b) {
  84. 		return get<2>(a) < get<2>(b);
  85. 	});
  86. }
  87.  
  88. int main()
  89. {
  90. 	int n, q;
  91. 	while (~scanf("%d%d", &n, &q))
  92. 	{
  93. 		for (int i = 0; i < n; ++i)
  94. 		{
  95. 			scanf("%d", &a[i]);
  96. 		}
  97. 		for (int k = 0; k < q; ++k)
  98. 		{
  99. 			scanf("%d%d", &get<0>(query[k]), &get<1>(query[k]));
  100.  
  101.  
  102. 			get<2>(query[k]) = k;
  103. 		}
  104.  
  105. 		moAlgorithm(n, a, q, query);
  106.  
  107. 		for (int k = 0; k < q; ++k)
  108. 		{
  109. 			printf("%d\n", get<3>(query[k]));
  110. 		}
  111. 	}
  112. 	return 0;
  113. }
Success #stdin #stdout 0s 6196KB
comments (?)
stdin
copy 
5 3
1 2 1 3 3
0 2
1 2
0 4
stdout
copy 
2
1
2
https://ideone.com/SM1bnE
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!