线段树之应用 ---- #1299 : 打折机票

#1299 : 打折机票

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

因为思念新宿的"小姐姐"们,岛娘计划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
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
const int N = 100000;

struct tree
{
	int left, right;
	int maxn;
}s[4 * N]; //一般长度为N的区间,所需节点个数不超过四倍

int a[N];

inline int Max(int a, int b) {
	return a > b ? a : b;
}

void build(int l, int r, int p)
{
	s[p].left = l;
	s[p].right = r;
	if (l == r)
	{
		s[p].maxn = a[l]; //在长度为0的节点处设置maxn
		return;
	}

	int mid = (l + r) / 2;
	build(l, mid, p << 1); //左孩子
	build(mid + 1, r, p << 1 | 0X01); //右孩子

	s[p].maxn = Max(s[p << 1].maxn, s[p << 1 | 0x01].maxn);
}

int search(int l, int r, int p)
{
	if (l <= s[p].left && s[p].right <= r) //如果查询区间包含当前区间
	{
		return s[p].maxn;
	}
	int mid = (s[p].left + s[p].right) / 2;
	if (l > mid) //全在右区间
		return search(l, r, p << 1 | 1);
	else if (r <= mid) //全在左区间
		return search(l, r, p << 1);
	else
		return Max(search(l, mid, p << 1), search(mid + 1, r, p << 1 | 0x01));
}

int main()
{
	int n, m;

	scanf("%d%d", &n, &m);
	memset(a, 0, sizeof(a));

	int t, v;
	for (int i = 0; i<n; i++)
	{
		scanf("%d%d", &t, &v);
		a[t] = Max(a[t], v);
	}

	build(1, 100000, 1); //创建线段树

	int l, r;
	for (int i = 0; i<m; i++)
	{
		scanf("%d%d", &l, &r);
		int ans = search(l, r, 1);
		if (!ans)
			printf("None\n");
		else
			printf("%d\n", ans);
	}

	return 0;
}
时间: 05-12

线段树之应用 ---- #1299 : 打折机票的相关文章

hihocoder 1299 打折机票 线段树

题目链接:http://hihocoder.com/problemset/problem/1299 code: //线段树 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define maxn 100005 using namespace std; int price[maxn]; int Max[maxn]; int segTree[4*maxn

HIHO Coder - 1299 打折机票

描述 因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包.经过了几天的夜战,岛娘终于在体力耗尽之前,用Python抓下了所有6月份,上海至东京的全部共 n 张机票.现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的,最贵的机票. 输入 输入数据的第一行包含两个整数 n,?m(1?≤?n,?m?≤?105),分别表示机票的总数,和询问的总数.接下来的 n 行,每行两个整数 t,?v (1?≤?t,?v?≤?105),表示每张机票出发的时间和价格. 接下来的

hihocode #1299 打折机票

题意很简单就是给你两个数n和m,n表示有n张飞机票,m表示有m次查询,接下来n行,每行两个数,分别表示航班出发的时间和价格,接下来m行,每行两个数表示查询这两个数时间内航班最贵的价格.如果没有要求的机票就输出"None".这道题是一道典型的RMQ问题,就是区间最值查询问题.这里提供两种解法. 1.线段树可以解决,而且是一道线段树的裸题. //segment tree #include <iostream> #include <cstdio> #include &

[HIHO1299]打折机票(线段树)

题目链接:http://hihocoder.com/problemset/problem/1299 线段树,按照t为下标去更新v,更新的时候要保留最大的那个. 1 #include <algorithm> 2 #include <iostream> 3 #include <iomanip> 4 #include <cstring> 5 #include <climits> 6 #include <complex> 7 #include

codevs 1299 线段树 区间更新查询

1299 切水果 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题解 查看运行结果 题目描述 Description 简单的说,一共N个水果排成一排,切M次,每次切[L,R]区间的所有水果(可能有的水果被重复切),每切完一次输出剩下水果数量 数据已重新装配,不会出现OLE错误 时限和数据范围适当修改,避免数据包过大而浪费空间资源 输入描述 Input Description 第1行共包括2个正整数,分别为N,M. 接下来m行每行两个正整数L,R 输出描述 

题目1 : 打折机票(hihoCoder挑战赛20)

题目1 : 打折机票 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包.经过了几天的夜战,岛娘终于在体力耗尽之前,用Python抓下了所有6月份,上海至东京的全部共 n 张机票.现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的,最贵的机票. 输入 输入数据的第一行包含两个整数 n,?m(1?≤?n,?m?≤?105),分别表示机票的总数,和询问的总数.接下来的 n 行,每行

题目1 : 打折机票(hihocoder 20挑战赛)

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 因为思念新宿的"小姐姐"们,岛娘计划6月份再去一趟东京,不过这次看来她需要自掏腰包.经过了几天的夜战,岛娘终于在体力耗尽之前,用Python抓下了所有6月份,上海至东京的全部共 n 张机票.现在请你帮助债台高筑的岛娘筛选出符合时间区间要求的,最贵的机票. 输入 输入数据的第一行包含两个整数 n,?m(1?≤?n,?m?≤?105),分别表示机票的总数,和询问的总数.接下来的 n 行,每行两个整数 t,?v (

[poj2104]可持久化线段树入门题(主席树)

解题关键:离线求区间第k小,主席树的经典裸题: 对主席树的理解:主席树维护的是一段序列中某个数字出现的次数,所以需要预先离散化,最好使用vector的erase和unique函数,很方便:如果求整段序列的第k小,我们会想到离散化二分和线段树的做法, 而主席树只是保存了序列的前缀和,排序之后,对序列的前缀分别做线段树,具有差分的性质,因此可以求任意区间的第k小,如果主席树维护索引,只需要求出某个数字在主席树中的位置,即为sort之后v中的索引:若要求第k大,建树时反向排序即可 1 #include

【BZOJ4942】[Noi2017]整数 线段树+DFS(卡过)

[BZOJ4942][Noi2017]整数 题目描述去uoj 题解:如果只有加法,那么直接暴力即可...(因为1的数量最多nlogn个) 先考虑加法,比较显然的做法就是将A二进制分解成log位,然后依次更新这log位,如果最高位依然有进位,那么找到最高位后面的第一个0,将中间的所有1变成0,那个0变成1.这个显然要用到线段树,但是复杂度是nlog2n的,肯定过不去. 于是我在考场上yy了一下,这log位是连续的,我们每次都要花费log的时间去修改一个岂不是很浪费?我们可以先在线段树上找到这段区间