Uva 11235
1 #include<stdio.h>
2 #include<math.h>
3 const int N = 100010;//區(qū)間最大長度
4 const int M = 32;
5 int d[N][M];//表示從i開始長度為2^j的一段元素中的最小值
6 int A[N];//元素
7 int n; //元素從1到n編號
8 int max(int a, int b) {
9 return a > b ? a : b;
10 }
11
12 int RMQ_init() {
13 for(int i = 1; i <= n; ++i) d[i][0] = A[i];
14 for(int j = 1; (1 << j) <= n; ++j)
15 for(int i = 1; i <= n + 1 - (1 << j); ++i)
16 d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
17 }
18
19 int RMQ_query(int l, int r) {
20 int k = 0;
21 while(1 << (k + 1) <= r - l + 1) ++k;
22 return max(d[l][k], d[r - (1 << k) + 1][k]);
23 }
24
25 int left[N], right[N], num[N], a[N];
26 int main() {
27 int m, q, l, r;
28 while(scanf("%d", &m), m) {
29 scanf("%d", &q);
30 n = 0;
31 int count = 1;
32 for(int i = 1; i <= m; ++i) {
33 scanf("%d", &a[i]);
34 }
35 a[m + 1] = a[m] + 1;
36 for(int i = 1; i <= m; ++i) {
37 if(a[i] != a[i + 1]) {
38 A[++n] = count;
39 for(int j = i - count + 1; j <= i; ++j) {
40 left[j] = i - count + 1;
41 right[j] = i;
42 num[j] = n;
43 }
44 count = 1;
45 }
46 else count++;
47 }
48 RMQ_init();
49 int ql, qr;
50 while(q--) {
51 int ans;
52 scanf("%d%d", &ql, &qr);
53 if(num[ql] == num[qr]) ans = qr - ql + 1;
54 else {
55 ans = max(right[ql] - ql + 1, qr - left[qr] + 1);
56 if(num[qr] - num[ql] > 1) ans = max(ans, RMQ_query(num[ql] + 1, num[qr] - 1));
57 }
58 printf("%d\n", ans);
59 }
60 }
61 return 0;
62 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/startgo/archive/2013/02/01/2889631.html
總結(jié)
- 上一篇： jquery easyUi简单介绍
- 下一篇： 用boost.signal实现多播委托