poj3368（RMQ）

来自lrj。。
 1 // UVa11235 Frequent Values
 2 // Rujia Liu
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 
 8 const int maxn = 100000 + 5;
 9 const int maxlog = 20;
10 
11 // 区间最*大*值
12 struct RMQ {
13   int d[maxn][maxlog];
14   void init(const vector<int>& A) {
15     int n = A.size();
16     for(int i = 0; i < n; i++) d[i][0] = A[i];
17     for(int j = 1; (1<<j) <= n; j++)
18       for(int i = 0; i + (1<<j) - 1 < n; i++)
19         d[i][j] = max(d[i][j-1], d[i + (1<<(j-1))][j-1]);
20   }
21 
22   int query(int L, int R) {
23     int k = 0;
24     while((1<<(k+1)) <= R-L+1) k++; // 如果2^(k+1)<=R-L+1，那么k还可以加1
25     return max(d[L][k], d[R-(1<<k)+1][k]);
26   }
27 };
28 
29 int a[maxn], num[maxn], left[maxn], right[maxn];
30 RMQ rmq;
31 int main() {
32   int n, q;
33   while(scanf("%d%d", &n, &q) == 2) {
34     for(int i = 0; i < n; i++) scanf("%d", &a[i]);
35     a[n] = a[n-1] + 1; // 哨兵
36     int start = -1;
37     vector<int> count;
38     for(int i = 0; i <= n; i++) {
39       if(i == 0 || a[i] > a[i-1]) { // 新段开始
40         if(i > 0) {
41           count.push_back(i - start);
42           for(int j = start; j < i; j++) {
43             num[j] = count.size() - 1; left[j] = start; right[j] = i-1;
44           }
45         }
46         start = i;
47       }
48     }
49     rmq.init(count);
50     while(q--) {
51       int L, R, ans;
52       scanf("%d%d", &L, &R); L--; R--;
53       if(num[L] == num[R]) ans = R-L+1;
54       else {
55         ans = max(R-left[R]+1, right[L]-L+1);
56         if(num[L]+1 < num[R]) ans = max(ans, rmq.query(num[L]+1, num[R]-1));
57       }
58       printf("%d
", ans);
59     }
60   }
61   return 0;
62 }