本文共 1441 字,大约阅读时间需要 4 分钟。
第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
773RMQ问题,直接的有O(n^2)的做法,可以压缩空间有O(nlogn)的做法,还有更好的线段树的做法,这里采用O(nlogn)的做法:
#include#include #include #include #define MAX 10005/*方法2: ST算法 M[ i ][ j ] 是以i 开始,长度为 2^j 的子数组的最小值的索引 分两个区间,M[i][j]为这两个区间最值的索引 则M[i][j]={M[i][j-1],M[i+2^(j-1)+1][j-1]} 构造M时间复杂度O(nlogn) 如何求区间的最值RMQ[i][j]? 设k=log(j-i+1) RMQ[i][j]={M[i][k],M[j-2^k+1][k]} 时间复杂度O(1) */ void RMQ2(int M[][15], int A[], int N) { int i, j; //initialize M for the intervals with length 1 for (i = 0; i < N; i++) M[i][0] = i; //compute values from smaller to bigger intervals for (j = 1; 1 << j <= N; j++) for (i = 0; i + (1 << j) - 1 < N; i++) if (A[M[i][j - 1]] > A[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1]; else M[i][j] = M[i + (1 << (j - 1))][j - 1]; } int M[MAX][15]; int S[MAX];int main(){#ifndef WANGCHUAN freopen("C:\\in.txt","r",stdin);#endif int n,q; scanf("%d",&n); for(int i=0;i
转载地址:http://ncvvi.baihongyu.com/