HiHoCoder 1299 打折机票 线段树

2017/04/01 Algorithm

tips: HiHocoder打折机票数据结构的经典应用。

HiHoCoder题目链接:#1299 : 打折机票

描述

因为思念新宿的”小姐姐”们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包。经过了几天的夜战,岛娘终于在体力耗尽之前,用Python抓下了所有6月份,上海至东京的全部共 n 张机票。现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的,最贵的机票。

输入

输入数据的第一行包含两个整数 n, m(1 ≤ n, m ≤ 105),分别表示机票的总数,和询问的总数。接下来的 n 行,每行两个整数 t, v (1 ≤ t, v ≤ 105),表示每张机票出发的时间和价格。 接下来的 m 行,每行两个整数 a, b (1 ≤ a ≤ b ≤ 105),表示每个询问所要求的时间区间。

输出

对于每组询问,输出一行表示最贵的价格。如果没有符合要求的机票,输出一行”None”。

样例输入

7 6
1 1
2 1
4 3
4 4
4 5
6 9
7 9
1 7
1 2
6 7
3 3
4 4
5 5

样例输出

9
1
9
None
5
None

分析

求数据在某个区间的特性问题,典型的区间树问题

源代码

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	static class SegmentTreeNode{
		int left;
		int right;
		int max;
		
		SegmentTreeNode leftSon;
		SegmentTreeNode rightSon;
		
		public SegmentTreeNode(int left, int right){
			this.left = left;
			this.right = right;
			
			this.max = Integer.MIN_VALUE;
		}
	}
	
	private int retriveMax(int left, int right, SegmentTreeNode root){
		if(root == null){
			return Integer.MIN_VALUE;
		}
		
		if(left == root.left && right == root.right){
			return root.max;
		}
		
		int mid = root.left + (root.right - root.left) / 2;
		
		if(right <= mid){
			return retriveMax(left, right, root.leftSon);
		}else if(left > mid){
			return retriveMax(left, right, root.rightSon);
		}else{
			int max1 = retriveMax(left, mid, root.leftSon);
			int max2 = retriveMax(mid + 1, right, root.rightSon);
			
			return max1 > max2 ? max1 : max2;
		}
	}
	
	private int insert(int time, int value, SegmentTreeNode root){
		if(root.left == root.right){
			root.max = root.max > value ? root.max : value;
			return root.max;
		}
		
		int mid = root.left + (root.right - root.left) / 2;
		if(time <= mid){
			if(root.leftSon == null){
				root.leftSon = new SegmentTreeNode(root.left, mid);
			}
			
			int tmp = insert(time, value, root.leftSon);
			root.max = root.max > tmp ? root.max : tmp;
		}else{
			if(root.rightSon == null){
				root.rightSon = new SegmentTreeNode(mid + 1, root.right);
			}
			int tmp = insert(time, value, root.rightSon);
			
			root.max = root.max > tmp ? root.max : tmp;
		}
		
		return root.max;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = null;
		
		scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		
		SegmentTreeNode root = new SegmentTreeNode(1, 100000);
		
		Main main = new Main();
		
		while(n-- > 0){
			int t = scanner.nextInt();
			int v = scanner.nextInt();
			
			main.insert(t, v, root);
		}
		
		while(m-- > 0){
			int a = scanner.nextInt();
			int b = scanner.nextInt();
			
			int res = main.retriveMax(a, b, root);
			
			if(res > 0){
				System.out.println(res);
			}else{
				System.out.println("None");
			}
		}

	}

}

Search

    Table of Contents