poj3264

链接:poj3264

题解

  • 区间最值,先上线段树做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#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做法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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 long
using 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;
}