# 线段树练习POJ 3264

Sample Input

6 3  (六只奶牛，下面分别是它们的身高，3个区间)
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output

6
3
0

```import java.io.StreamTokenizer;
import java.io.PrintWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

class tree{  //线段树节点
int left,right,maxvalue,minvalue;
}

public class Main{
tree[] tt;//线段树,用数组实现

int height[];//奶牛身高

public Main(int[] height){
this.height=height;
tt=new tree[131070];
for(int i=0;i<131070;i++)
//数组大小的计算参看:http://128kj.iteye.com/blog/1739064
tt[i]=new tree();
}

private void built_tree(int lp,int rp,int pos){  //构建以pos为根的线段树
tt[pos].left=lp;
tt[pos].right=rp;
if(lp==rp){
tt[pos].maxvalue=height[rp];
tt[pos].minvalue=height[lp];
return ;
}
int mid=(tt[pos].left+tt[pos].right)>>1;
built_tree(lp,mid,pos<<1);
built_tree(mid+1,rp,pos<<1|1);
tt[pos].maxvalue=Math.max(tt[pos<<1].maxvalue,tt[pos<<1|1].maxvalue);
tt[pos].minvalue=Math.min(tt[pos<<1].minvalue,tt[pos<<1|1].minvalue);
}

//找[lp,rp]上的最大值
private int findmax(int lp,int rp,int pos){
if(tt[pos].left==lp&&tt[pos].right==rp){
return tt[pos].maxvalue;
}

int mid=(tt[pos].left+tt[pos].right)>>1;
if(rp<=mid){
return findmax(lp,rp,pos<<1);
}
else if(lp>mid)
return findmax(lp,rp,pos<<1|1);
else{
return Math.max( findmax(lp,mid,pos<<1), findmax(mid+1,rp,pos<<1|1));
}
}

//找[lp,rp]上的最小值
private int findmin(int lp,int rp,int pos){
if(tt[pos].left==lp&&tt[pos].right==rp){
return tt[pos].minvalue;
}
int mid=(tt[pos].left+tt[pos].right)>>1;
if(rp<=mid)
return findmin(lp,rp,pos<<1);
else if(lp>mid)
return findmin(lp,rp,pos<<1|1);
else
return Math.min( findmin( lp,mid,pos<<1 ),findmin( mid+1,rp,pos<<1|1 ) );
}

public static void  main(String args[]) throws IOException{
StreamTokenizer st = new StreamTokenizer(new BufferedReader(
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

while(st.nextToken() != StreamTokenizer.TT_EOF) {

int n=(int) st.nval;
st.nextToken();
int q=(int) st.nval;
int[] height=new int[n+1];
for(int i=1;i<=n;++i){
st.nextToken();
height[i]=(int) st.nval;
}

Main ma=new Main(height);
ma.built_tree(1,n,1);
int x,y;
while(q-->0){
st.nextToken();
x=(int) st.nval;
st.nextToken();
y=(int) st.nval;
int mmax=ma.findmax(x,y,1);
int mmin=ma.findmin(x,y,1);
System.out.printf("%d\n",mmax-mmin);
}
out.flush();

}
}
}
```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

Mayor's posters Description The citizens of Bytetown, AB, could not stand that the candidates

Stars Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26354 Accepted: 11498 Descri
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 9712 Accepted: 4679 De
Mayor's posters Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 34272 Accepted: 99

http://poj.org/problem?id=2828 一开始敲了个splay，直接模拟。 tle了。。 常数太大。。 好吧，说
Buy Tickets Time Limit: 4000MS Memory Limit: 65536K Total Submissions: 13017 Accepted: 6449 D