POJ3264 比较裸的区间最值问题。用线段树或者ST表都可以。此处我们用ST表解决。
ST表建表方法采用动态规划的方法, ST[I][J]表示数组从第I位到第 I+2^J-1 位的最值,用二分的思想建立动规方程。
查询方法就不用说了 非常简单。
我这个查询写的稍微有点问题, 理想的ST表查询应该是O(1)的 我写成了O(logn)
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<vector> #include<queue> #include<algorithm> const int maxn=50000+1,maxq=200000; int stmax[maxn][17],stmin[maxn][17],hei[maxn],n,q; using namespace std; void build() { memset(stmax,0,sizeof(stmax));memset(stmin,0,sizeof(stmin)); for(int i=0;i<17;i++) for(int j=1;j<=n;j++) { int len=1<<i; if(j+len-1>n)break; len=len>>1; if(i==0){stmax[j][i]=stmin[j][i]=hei[j];continue;} stmax[j][i]=max(stmax[j][i-1],stmax[j+len][i-1]); stmin[j][i]=min(stmin[j][i-1],stmin[j+len][i-1]); } } int query(int val[][17],int l,int r,bool flag) { int len=(r-l+1),ans; if(flag)ans=1<<30; else ans=0; int tot=0,lp=1; while(len>0&&tot<17&&(l+(1<<tot))<=r+1) { if((len%2)==0){tot++;len=len>>1;lp=lp<<1;continue;} if(flag)ans=min(ans,val[l][tot]); else ans=max(ans,val[l][tot]); tot++;len=len>>1;l+=lp;lp=lp<<1; } return ans; } int main() {freopen("t.txt","r",stdin); scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) scanf("%d",&hei[i]); build(); int l,r; for(int i=0;i<q;i++) { scanf("%d%d",&l,&r); printf("%d ",query(stmax,l,r,0)-query(stmin,l,r,1)); } return 0; }