HIHO Coder - 1299 打折机票

本文主要是介绍HIHO Coder - 1299 打折机票，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

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

输入

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

输出

对于每组询问，输出一行表示最贵的价格。如果没有符合要求的机票，输出一行"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

时间限制: 10000ms

单点时限: 1000ms

内存限制: 256MB

PS.真的很想吐槽那个图=日=

这是一个静态的线段树问题。

#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;const int maxn = 1e6+7;
int a[maxn];
struct node
{int l, r, x;
}tickt[maxn*4];void BuildTree(int x, int left, int right)
{tickt[x].l = left;tickt[x].r = right;if (left == right){tickt[x].x = a[left];return;}int mid = (left+right) >> 1;BuildTree(x<<1, left, mid);BuildTree(x<<1|1, mid+1, right);tickt[x].x = max(tickt[x<<1].x, tickt[x<<1|1].x);
}
int query(int x, int left, int right)
{if(left <= tickt[x].l && tickt[x].r <= right)return tickt[x].x;int ans = 0;int mid = (tickt[x].l + tickt[x].r) >> 1;if (mid >= left) ans = max(ans, query(x<<1, left, right));if (mid < right) ans = max(ans, query(x<<1|1, left, right));return ans;
}
int main()
{int m, n;scanf("%d %d", &n, &m);memset(a, 0, sizeof(a));for(int i = 1; i <= n; i++){int x, y;scanf("%d %d", &x, &y);a[x] = max(a[x], y);}BuildTree(1, 1, 100000);for(int i = 1; i <= m; i++){int from, to;scanf("%d %d", &from, &to);int p = query(1, from, to);if(p == 0)printf("None\n");elseprintf("%d\n", p);}return 0;
}

这篇关于HIHO Coder - 1299 打折机票的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---