给出一个有N个数的序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，最大的数是多少。

 

例如: 1 7 6 3 1。i = 1, j = 3，对应的数为7 6 3，最大的数为7。（该问题也被称为RMQ问题）

 收起

 

输入

第1行：1个数N，表示序列的长度。(2 <= N <= 10000)第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S[i] <= 10^9)第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 10000)第N + 3 - N + Q + 2行：每行2个数，对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1)

输出

共Q行，对应每一个查询区间的最大值。

输入样例

51763130 11 33 4

输出样例

773 典型rmq问题，st算法。 代码：

#include 
       
        #include 
        
         using namespace std;int dp[10001][20];int n,q,qi,qj;void init() {    for(int j = 1;j < 14;j ++) {
     ///预处理        for(int i = 0;i < n;i ++) {            if(i + (1 << j) <= n) {                dp[i][j] = max(dp[i][j - 1],dp[i + (1 << (j - 1))][j - 1]);            }        }    }}int min_2(int x) {    int d = 1,c = 0;    while(d * 2 <= x) d *= 2,c ++;    return c;}int RMQ(int l,int r) {    int len = min_2(r - l + 1);    return max(dp[l][len],dp[r - (1 << len) + 1][len]);}int main() {    scanf("%d",&n);    for(int i = 0;i < n;i ++) {        scanf("%d",&dp[i][0]);    }    init();    scanf("%d",&q);    for(int i = 0;i < q;i ++) {        scanf("%d%d",&qi,&qj);        printf("%d\n",RMQ(qi,qj));    }}
        
       

 线段树。

代码：

#include 
       
        #include 
        
         using namespace std;int tr[40001],mtr[40001];int n,q,qi,qj;void build(int l,int r,int t) {    if(l == r) {        scanf("%d",&tr[t]);        mtr[t] = tr[t];    }    else {        int mid = (l + r) >> 1;        build(l,mid,t << 1);        build(mid + 1,r,t << 1 | 1);        mtr[t] = max(mtr[t << 1],mtr[t << 1 | 1]);    }}int query(int x,int y,int l,int r,int t) {    if(l >= x && r <= y) return mtr[t];    int mid = (l + r) >> 1,max_ = 0;    if(mid < y) max_ = max(max_,query(x,y,mid + 1,r,t << 1 | 1));    if(mid >= x) max_ = max(max_,query(x,y,l,mid,t << 1));    return max_;}int main() {    scanf("%d",&n);    build(1,n,1);    scanf("%d",&q);    for(int i = 0;i < q;i ++) {        scanf("%d%d",&qi,&qj);        printf("%d\n",query(qi + 1,qj + 1,1,n,1));    }}