帮别人做违法网站会判刑吗/搜狗搜索引擎网页

RMQ简介

含有倍增,分治,DP思想
可以O(nlog n)初始化O(1)查询
求区间最值
离线算法

初始化

对于一个数组a[n]
[i,j]的区间最值可以分割成
求[i,k],[k,j]的最值
这里我们引入倍增思想,设k=log2(j-i+1)(向下取整)
就是求[i,i+2^k],[j-2^k+1,j]的最值
为什么可以这么分呢?
因为i+2^k<=j
而且j-2^k>=i
重复区间最值不影响[i,j]最值
那么倍增+DP就可以的出得来了
设f[n][j]为原数组从n到2^j的最值
f[n][j]=max(f[n][j-1],f[n+2^j/2][j-1])
又因为2^0=1
所以初始化方程就可以出来了f[i][0]=a[i]

如果你不知道倍增

其实就是二进制优化啦

求区间最值

其实上面讲过.
求[i,j]区间最值
就是求[i,i+2^k],[j-2^k+1,j]最值,k=log2(j-i+1)(向下取整)
倍增=>求[i,k],[j-2^k,k]最值

一个简单的小优化

求2^k时可以有两个小优化
可以打表2^k
也可以位运算
还可以快速幂 PS.应该没人用吧..

Talk is cheap,show me the code

http://poj.org/problem?id=3264

#include <iostream>
#include <stdio.h>
#include <math.h>
#define N 50000
using namespace std;
int maxn[N+100][17],minn[N+100][17];
int n,q;
int main(){scanf("%d%d",&n,&q);for (int i=1;i<=n;i++)scanf("%d",&maxn[i][0]),minn[i][0]=maxn[i][0];for (int j=1;j<=16;j++)for (int i=1;i<=n;i++)if (i+(1<<j)-1<=n){maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);}for (int i=1;i<=q;i++){int a,b;scanf("%d%d",&a,&b);int k=log2(b-a+1);printf("%d\n",max(maxn[a][k],maxn[b-(1<<k)+1][k])-min(minn[a][k],minn[b-(1<<k)+1][k]));}
}