51nod 1174 区间中最大的数(线段树）

51nod 1174 区间中最大的数(线段树）

1174 区间中最大的数 基准时间限制：1 秒 空间限制：131072 KB 分值: 0 难度：基础题 收藏 关注 给出一个有N个数的序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，最大的数是多少。 例如: 1 7 6 3 1。i = 1, j = 3，对应的数为7 6 3，最大的数为7。（该问题也被称为RMQ问题） Input 第1行：1个数N，表示序列的长度。(2 <= N <= 10000) 第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S[i] <= 10^9) 第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 10000) 第N + 3 - N + Q + 2行：每行2个数，对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1) Output 共Q行，对应每一个查询区间的最大值。 Input示例 5 1 7 6 3 1 3 0 1 1 3 3 4 Output示例 7 7 3

以后要用java写算法~ 线段树模板题，很简单

import java.util.Scanner;public class Main { private Tree tree[]; public static void main(String[] args) { new Main().execute(); } private void execute() { Scanner sca=new Scanner(System.in); int n=sca.nextInt(); tree=new Tree[n*4]; buildTree(1,n,1,sca); int q=sca.nextInt(); while(q-->0){ int i=sca.nextInt(); int j=sca.nextInt(); System.out.println(query(1,i+1,j+1)); } } private long query(int root,int l,int r){ if(tree[root].getLeft()==l&&tree[root].getRight()==r){ return tree[root].getVal(); } int mid=(tree[root].getLeft()+tree[root].getRight())/2; if(mid>=r){ return query(root*2,l,r); }else if(mid

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。