题目链接：https://vjudge.net/problem/UVA-11235
题意：给一串不递减数字，q次询问，每次查询[l,r]内出现次数最多的数字出现的次数。
查询分两部分：一部分是[l,r]为同一个数的区间，另一部分则是在上下界处截取一部分的情况。
首先离散化，后用l[],r[],v[]分别记录每一段相同数字的左右区间和出现次数。v可以直接由r-l+1更新得到。
第一部分更新ret后，接下来的rmq分三部分：
第一部分查询左边界截取一部分的数字的当前长度，第二部分查询右边界的，第三部分查询删掉左右边界后中间完整的部分的最值。
ST表维护最值就好了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 const int maxn = 100100; 6 7 int n, m, q; 8 int a[maxn]; 9 int h[maxn], hcnt; 10 11 int l[maxn], r[maxn], v[maxn]; 12 int dp[maxn][33]; 13 14 void st(int* b) { 15 for(int i = 1; i <= m; i++) dp[i][0] = b[i]; 16 int k = int(log(n+1.0)/log(2.0)); 17 for(int j = 1; j <= k; j++) { 18 for(int i = 1; i + (1 << j) - 1 <= m; i++) { 19 dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); 20 } 21 } 22 } 23 24 int query(int l, int r) { 25 int k = int(log(r-l+1.0)/log(2.0)); 26 return max(dp[l][k], dp[r-(1<<k)+1][k]); 27 } 28 29 int id(int x) { 30 return lower_bound(h, h+hcnt, x) - h + 1; 31 } 32 33 int main() { 34 // freopen("in", "r", stdin); 35 while(~scanf("%d",&n) && n) { 36 scanf("%d", &q); 37 memset(l, 0, sizeof(l)); 38 memset(r, 0, sizeof(r)); 39 memset(v, 0, sizeof(v)); 40 m = -1; 41 int pre = -1, ll = 1, rr, cnt = 0; 42 for(int i = 1; i <= n; i++) { 43 scanf("%d", &a[i]); 44 h[i-1] = a[i]; 45 } 46 sort(h, h+n); hcnt = unique(h, h+n) - h; 47 for(int i = 1; i <= n; i++) a[i] = id(a[i]); 48 for(int i = 1; i <= n; i++) { 49 if(pre != a[i]) { 50 l[++m] = ll, r[m] = i - 1; 51 v[m] = r[m] - l[m] + 1; 52 pre = a[i]; 53 ll = i; 54 cnt = 1; 55 } 56 else rr++, cnt++; 57 } 58 l[++m] = ll, r[m] = n; 59 v[m] = r[m] - l[m] + 1; 60 st(v); 61 while(q--) { 62 scanf("%d %d", &ll, &rr); 63 if(a[ll] == a[rr]) { 64 cout << rr - ll + 1 << endl; 65 continue; 66 } 67 int ret = max(0, r[a[ll]]-ll+1); 68 ret = max(ret, rr-l[a[rr]]+1); 69 if(a[ll] + 1 <= a[rr] - 1) ret = max(ret, query(a[ll]+1, a[rr]-1)); 70 cout << ret << endl; 71 } 72 } 73 return 0; 74 }