poj3264 发表于 2018-04-07 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:poj3264 题解 区间最值,先上线段树做法 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define lson o<<1,l,mid#define rson o<<1|1,mid+1,r#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)using namespace std;typedef pair<int,int> s;const int N=1e6;s rt[N<<2];int n,m,a[N];inline void build(int o,int l,int r){ if(l==r){rt[o]=s(a[l],a[l]);return ;} int mid=l+r>>1; build(lson); build(rson); rt[o]=s(max(rt[o<<1].first,rt[o<<1|1].first),min(rt[o<<1].second,rt[o<<1|1].second));}inline int query(int o,int l,int r,int ll,int rr,int op){ if(l==ll&&r==rr)return op?rt[o].first:rt[o].second; int mid=l+r>>1; if(rr<=mid)return query(lson,ll,rr,op); else if(ll>mid) return query(rson,ll,rr,op); else { int x=query(lson,ll,mid,op); int y=query(rson,mid+1,rr,op); return op?max(x,y):min(x,y); }}int main(){ scanf("%d%d",&n,&m); rep(i,1,n)scanf("%d",&a[i]); build(1,1,n); rep(i,1,m){ int x,y; scanf("%d%d",&x,&y); int ans=query(1,1,n,x,y,1); ans-=query(1,1,n,x,y,0); printf("%d\n",ans); } return 0;} RMQ做法 1234567891011121314151617181920212223242526272829303132333435#include<cstdio>#include<cstdlib>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)#define ll long longusing namespace std;const int N=1e6;int mx[N][100],mn[N][100],a[N],n,m;void rmq(){ int end=log(n+0.0)/log(2.0); rep(i,1,n)mx[i][0]=mn[i][0]=a[i]; rep(j,1,end){ int end_i=n-(1<<j)+1; rep(i,1,end_i){ mx[i][j]=max(mx[i][j-1],mx[i+(1<<j-1)][j-1]); mn[i][j]=min(mn[i][j-1],mn[i+(1<<j-1)][j-1]); } }}int ask(int l,int r){ int k=log(r-l+1.0)/log(2.0); int ans1=max(mx[l][k],mx[r-(1<<k)+1][k]); int ans2=min(mn[l][k],mn[r-(1<<k)+1][k]); return ans1-ans2;}int main(){ scanf("%d%d",&n,&m); rep(i,1,n)scanf("%d",&a[i]); rmq(); while(m--){int x,y;scanf("%d%d",&x,&y);printf("%d\n",ask(x,y));} return 0;}