#1299 : 打折机票

题目连接：

http://hihocoder.com/problemset/problem/1299

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

9

1

9

None

5

None

题意

题解：

线段树的基础应用

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+7;

int a[maxn],n,m;

struct node{int l,r,x;}t[maxn*4];

void build(int x,int l,int r)

{

    t[x].l=l,t[x].r=r;

    if(l==r){t[x].x=a[l];return;}

    int mid=(l+r)/2;

    build(x<<1,l,mid);

    build(x<<1|1,mid+1,r);

    t[x].x=max(t[x<<1].x,t[x<<1|1].x);

}

int query(int x,int l,int r)

{

    int L=t[x].l,R=t[x].r;

    if(l<=L&&R<=r)return t[x].x;

    int ans=0,mid=(L+R)/2;

    if(mid>=l)ans=max(ans,query(x<<1,l,r));

    if(mid<r)ans=max(ans,query(x<<1|1,l,r));

    return ans;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        int x,y;scanf("%d%d",&x,&y);

        a[x]=max(a[x],y);

    }

    build(1,1,100000);

    for(int i=1;i<=m;i++)

    {

        int x,y;scanf("%d%d",&x,&y);

        int p=query(1,x,y);

        if(p==0)printf("None\n");

        else printf("%d\n",p);

    }

}

机票

hihocoder #1299 : 打折机票 线段树