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