fork download 
  1. /*
  2. Hanit Banga
  3. */
  4.  
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. #define pb push_back
  12. #define fast_cin() ios_base::sync_with_stdio(false)
  13.  
  14. typedef long long ll;
  15. typedef pair <int, int> pii;
  16. typedef pair <ll, ll> pll;
  17.  
  18. const int N = 5e5 + 5;
  19.  
  20. int a[N], occ[N][3], ans[N], tree[3*N];
  21. pii temp[N];
  22. vector <pii> query[N];
  23.  
  24. void updateTree(int i, int l, int r, int p, int val);
  25. int queryTree(int i, int l, int r, int ql, int qr);
  26.  
  27. int main()
  28. {
  29. 	int n, q;
  30. 	cin >> n >> q;
  31.  
  32. 	for (int i = 1; i <= n; ++i)
  33. 	{
  34. 		cin >> temp[i].first;
  35. 		temp[i].second = i;
  36. 	}
  37.  
  38. 	sort(temp + 1, temp + n + 1);
  39. 	int nxt = 1;
  40. 	a[temp[1].second] = 1;
  41. 	for (int i = 2; i <= n; ++i)
  42. 	{
  43. 		if (temp[i].first != temp[i - 1].first)
  44. 			++nxt;
  45.  
  46. 		a[temp[i].second] = nxt;
  47. 	}
  48.  
  49. 	for (int i = 1; i <= n; ++i)
  50. 		for (int j = 0; j < 3; ++j)
  51. 			occ[i][j] = -1;
  52.  
  53. 	// for (int i = 0; i < n; ++i)
  54. 	// 	cout << a[i] << ' ';
  55.  
  56. 	for (int i = 1; i <= q; ++i)
  57. 	{
  58. 		int l, r;
  59. 		cin >> l >> r;
  60. 		query[r].pb({l, i});
  61. 	}
  62.  
  63. 	for (int r = 1; r <= n; ++r)
  64. 	{
  65. 		int cur = a[r];
  66. 		if (occ[cur][0] == -1)
  67. 			occ[cur][0] = r;
  68.  
  69. 		else if (occ[cur][1] == -1)
  70. 		{
  71. 			occ[cur][1] = occ[cur][0];
  72. 			occ[cur][0] = r;
  73. 			updateTree(1, 1, n, occ[cur][1], 1);
  74. 		}
  75.  
  76. 		else if (occ[cur][2] == -1)
  77. 		{
  78. 			for (int i = 2; i >= 1; --i)
  79. 				occ[cur][i] = occ[cur][i-1];
  80.  
  81. 			occ[cur][0] = r;
  82. 			updateTree(1, 1, n, occ[cur][2], -2);
  83. 			updateTree(1, 1, n, occ[cur][1], 1);
  84. 		}
  85.  
  86. 		else
  87. 		{
  88. 			updateTree(1, 1, n, occ[cur][2], 1);
  89. 			for (int i = 2; i >= 1; --i)
  90. 				occ[cur][i] = occ[cur][i-1];
  91.  
  92. 			occ[cur][0] = r;
  93. 			updateTree(1, 1, n, occ[cur][2], -2);
  94. 			updateTree(1, 1, n, occ[cur][1], 1);
  95. 		}
  96.  
  97. 		for (auto &i : query[r])
  98. 			ans[i.second] = queryTree(1, 1, n, i.first, r);
  99. 	}
  100.  
  101. 	for (int i = 1; i <= q; ++i)
  102. 		cout << ans[i] << '\n';
  103. }
  104.  
  105. void updateTree(int i, int l, int r, int p, int val)
  106. {
  107. 	if (p < l or p > r)
  108. 		return;
  109.  
  110. 	tree[i] += val;
  111. 	if (l == r)
  112. 		return;
  113.  
  114. 	int mid = (l + r) / 2;
  115. 	updateTree(2*i, l, mid, p, val);
  116. 	updateTree(2*i + 1, mid + 1, r, p, val);
  117. }
  118.  
  119. int queryTree(int i, int l, int r, int ql, int qr)
  120. {
  121. 	if (qr < l or ql > r)
  122. 		return 0;
  123.  
  124. 	if (ql <= l and r <= qr)
  125. 		return tree[i];
  126.  
  127. 	int mid = (l + r) / 2;
  128. 	return queryTree(2*i, l, mid, ql, qr) + queryTree(2*i + 1, mid + 1, r, ql, qr);
  129. }
Runtime error #stdin #stdout 0.03s 28864KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/revN6j
language:
C++14 (gcc 8.3)
created:
7 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!