高度平衡
Time Limit:10000MS Memory Limit:65536K
Total Submit:108 Accepted:95
Case Time Limit:1000MS
Description
在每天擠奶的時候，農民約翰的N頭牛（1≤n≤50000）總是排成一列。有一天，約翰決定與他的牛們一起玩一個極限飛盤遊戲。為了簡單起見，他将從奶牛隊列裡面選一定範圍内的奶牛來玩這個遊戲。然而所有的牛對這個遊戲都很感興趣。農民約翰列出了Q份名單（1≤Q≤200000）和每個奶牛的高度（1≤高度≤1000000）。對于每一份名單，他想你幫助他确定在每份名單中高度最高的奶牛與高度最低的奶牛的高度差是多少。
Input
第一行為N(1≤N≤50000)和Q(1≤Q≤200000)；從第2行到第N+1行，每行一個數字，表示第i頭牛的高度(1≤height≤1000000)；從第N+2行到第N+Q+1行，每行兩個整數A和B(1≤A≤B≤N)，表示從第A頭牛到第B頭牛的範圍。
Output
從第一行到第Q行，每行一個整數，表示從第A頭牛到第B頭牛之間，最高牛與最矮牛的高度差。
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Source
USACO 2007 January Silver
——————————————————————————————————————————————————————————————————
法一：線段樹；
#include<cstdio>
const int inf=100000000;
struct node{int a,b,l,r,min,max;};
node tree[1000005];
int tot,a[500005];
int min(int x,int y)
{
if(x<y)return x;
else return y;
}
int max(int x,int y)
{
if(x>y)return x;
else return y;
}
void make(int x,int y)
{
int i=++tot;
tree[i].a=x,tree[i].b=y,tree[i].min=inf,tree[i].max=0;
if(x<y)
{
tree[i].l=tot+1;make(x,(x+y)/2);
tree[i].r=tot+1;make((x+y)/2+1,y);
tree[i].max=max(tree[tree[i].l].max,tree[tree[i].r].max);
tree[i].min=min(tree[tree[i].l].min,tree[tree[i].r].min);
}
else tree[i].max=tree[i].min=a[x];
}
int find_min(int i,int x,int y)
{
if(tree[i].a>y||tree[i].b<x)return inf;
if(tree[i].a>=x&&tree[i].b<=y)return tree[i].min;
else
{
int t=inf;
if(tree[i].l)t=min(t,find_min(tree[i].l,x,y));
if(tree[i].r)t=min(t,find_min(tree[i].r,x,y));
return t;
}
}
int find_max(int i,int x,int y)
{
if(tree[i].a>y||tree[i].b<x)return 0;
if(tree[i].a>=x&&tree[i].b<=y)return tree[i].max;
else
{
int t=0;
if(tree[i].l)t=max(t,find_max(tree[i].l,x,y));
if(tree[i].r)t=max(t,find_max(tree[i].r,x,y));
return t;
}
}
int main()
{
int i,j,n,x,y,q;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
make(1,n);
for(i=1;i<=q;i++)
{
scanf("%d%d",&x,&y);
int t,tt;
t=find_min(1,x,y);
tt=find_max(1,x,y);
printf("%d\n",tt-t);
}
return 0;
}
法二：倍增（很經典！！！）
預處理：
dp思想：dp[i][j]表示從i起連續2^j個數中最小值（即表示區間[i,i+2^j-1]）;
如；數列3,2,4,5,6,8,1,2,9,7；f[1][0]=3，f[1][1]=2，f[1][2]=2，f[1][3]=1，f[2][0]=2，f[2][1]=2，f[2][2]=2……
f[i][j]=min(f[i][j-1],f[i+2^(j-1)][j-1]);
ps:别問我怎麼想到的！因為沒學根本想不到，記住就好.;
詢問：
區間[x,y]可以分成[x,x+2^k-1]和[y-2^k+1,y];
即f[x][k]和f[y-(1<<k)+1][k];
k=floor(log(y-x+1)/log(2));
_______________________________________________ 以下為代碼表示______________________________________________________________________
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define inf 1<<30
using namespace std;
int dpmax[50005][20],n,m,dpmin[50005][20];
int main()
{
int i,j,x,y,Max,Min,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&dpmin[i][0]);
dpmax[i][0]=dpmin[i][0];
}
for(j=1;j<=floor(log(n)/log(2));j++)
for(i=1;i<=(n-(1<<j)+1);i++)
{
dpmin[i][j]=min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]);
dpmax[i][j]=max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]);
}
for(i=1;i<=m;i++)
{
Max=0;Min=inf;
scanf("%d%d",&x,&y);
k=floor(log(y-x+1)/log(2));
Max=max(dpmax[x][k],dpmax[y-(1<<k)+1][k]);
Min=min(dpmin[x][k],dpmin[y-(1<<k)+1][k]);
printf("%d\n",Max-Min);
}
return 0;
}