网站是做java还是c/seo关键词优化公司哪家好

算法入门经典训练指南198页。

范围最小值问题(Range Minimum Query,RMQ).实践中最常用的是Sparse Table 算法，预处理时间是O(nlogn),查询只需要O(1)，而且常数很小。

注意到整个数组是非降序的，所有相等元素会聚集到一起。这样可以把整个数组进行游程编码。比如-1,1,1,2,,2,2,4可以编码成（-1,1）(1,2),(2,3),(4,1),其中(a,b)表示有b个连续的a.

#include <iostream>
#include <map>
#include <deque>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int m=100005;
int a[m],l[m],r[m],num[m],d[m][30];
void RMQ_init(const vector<int>&A)
{int i,j,n=A.size();for(i=0; i<n; i++)d[i][0]=A[i];for(j=1; (1<<j)<=n; j++)for(i=0; i+(1<<j)-1<n; i++)d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}
int RMQ(int L,int R)
{int k=0;while((1<<(k+1))<=R-L+1) k++;return max(d[L][k],d[R-(1<<k)+1][k]);
}
int main()
{int n,q,i,j;while(scanf("%d",&n),n){scanf("%d",&q);for(i=0; i<n; i++)scanf("%d",&a[i]);a[n]=a[n-1]+1;int start=-1;vector<int>count;for(i=0; i<=n; i++)if(a[i]>a[i-1]){if(i!=0){count.push_back(i-start);for(j=start; j<i; j++){num[j]=count.size()-1;l[j]=start;r[j]=i-1;}start=i;}}RMQ_init(count);while(q--){int L,R,sum;scanf("%d%d",&L,&R);L--;R--;if(num[L]==num[R]) sum=R-L+1;else{sum=max(r[L]-L+1,R-l[R]+1);if(num[L]+1<=num[R]-1)sum=max(sum,RMQ(num[L]+1,num[R]-1));}printf("%d\n",sum);}}return 0;
}