fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. const int maxn = 100010;
  8. int val[maxn];
  9.  
  10. struct SegNode {
  11. 	int left, right, len;
  12. 	int leftLen, rightLen;
  13. 	int mid() {
  14. 		return (left + right) >> 1;
  15. 	}
  16. };
  17.  
  18. struct SegmentTree {
  19.  
  20. 	SegNode tree[maxn*5];
  21.  
  22. 	void build(int left, int right, int idx) {
  23. 		tree[idx].left = left; 
  24. 		tree[idx].right = right;
  25. 		if (left == right) {
  26. 			tree[idx].leftLen = 1;
  27. 			tree[idx].rightLen = 1;
  28. 			tree[idx].len = 1;
  29. 			return ;
  30. 		}
  31. 		int mid = tree[idx].mid();
  32. 		build(left, mid, idx<<1);
  33. 		build(mid+1, right, idx<<1|1);
  34.  
  35. 		//pushup
  36. 		if (val[mid] == val[mid+1]) {
  37. 			if (val[left] == val[mid])
  38. 				tree[idx].leftLen = tree[idx<<1].leftLen + tree[idx<<1|1].leftLen;
  39. 			else
  40. 				tree[idx].leftLen = tree[idx<<1].leftLen;
  41. 			if (val[right] == val[mid+1])
  42. 				tree[idx].rightLen = tree[idx<<1|1].rightLen + tree[idx<<1].rightLen;
  43. 			else 
  44. 				tree[idx].rightLen = tree[idx<<1|1].rightLen;
  45. 			int tmp = tree[idx<<1].rightLen + tree[idx<<1|1].leftLen;
  46. 			tree[idx].len = max(tmp, max(tree[idx<<1].len, tree[idx<<1|1].len));
  47. 		} else {
  48. 			tree[idx].leftLen = tree[idx<<1].leftLen;
  49. 			tree[idx].rightLen = tree[idx<<1|1].rightLen;
  50. 			tree[idx].len = max(tree[idx<<1].len, tree[idx<<1|1].len);
  51. 		}
  52. 	}
  53.  
  54. 	int query(int left, int right, int idx) {
  55. 		if (tree[idx].left >= left && tree[idx].right <= right)
  56. 			return tree[idx].len;
  57. 		int mid = tree[idx].mid();
  58. 		if (right <= mid) 
  59. 			return query(left, right, idx<<1);
  60. 		else if (left > mid) 
  61. 			return query(left, right, idx<<1|1);
  62. 		else {
  63. 			int tmp = query(left, mid, idx<<1);
  64. 			int tem = query(mid+1, right, idx<<1|1);
  65. 			if (val[mid] == val[mid+1]) {
  66. 				int temp = min(tree[idx<<1].rightLen, mid - left + 1) + 
  67. 					min(tree[idx<<1|1].leftLen, right - mid);
  68. 				return max(temp, max(tmp, tem));
  69. 			} else {
  70. 				return max(tmp, tem);
  71. 			}
  72. 		}
  73. 	}
  74. };
  75. SegmentTree seg;
  76.  
  77. int main() {
  78. 	int n, q;
  79. 	while (~scanf("%d", &n)) {
  80. 		if (n == 0) break;
  81. 		scanf("%d", &q);
  82. 		for (int i = 1; i <= n; i++)
  83. 			scanf("%d", &val[i]);
  84. 		seg.build(1, n, 1);
  85. 		for (int i = 0; i < q; i++) {
  86. 			int left, right;
  87. 			scanf("%d %d", &left, &right);
  88. 			if (left == right) puts("1");
  89. 			else printf("%d\n", seg.query(left, right, 1));
  90. 		}
  91. 	}
  92. 	return 0;
  93. }
  94.  
Success #stdin #stdout 0s 13016KB
comments (?)
stdin
copy 
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
stdout
copy 
1
4
3
https://ideone.com/nGIts7
SPOJ FREQUENT
language:
C++ (gcc 8.3)
created:
11 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!