SPOJ BGSHOOT

BGSHOOT - Shoot and kill

no tags

The problem is about Mr.BG who is a great hunter. Today he has gone to a dense forest for hunting and killing animals.

Sadly, he has only one bullet in his gun. He wants to kill as many animals as possible with only one bullet.

He has already known the information of duration availability of all animals of the forest.

So, he is planning to shoot at a time so that he could kill maximum animal.

Input

Input begins with an integer N denoting total numbers of animals.

Next N lines contains the duration of availability of animal denoting by X (Starting time) and Y (Ending time) .

Then, there will be Q, denoting the total numbers of queries to be answer.

Each query giving two integer L and R, L denoting the time hunter will come to forest and begins shooting

and R denoting last time upto which he will stay at forest for hunting.

Output

For each query output an integer denoting maximum numbers of animals he could kill by shooting at a time during L and R (inclusive).

Constraints:

1<=N,Q<=100000

1<=X,Y,L,R<=1000000000

Example

Input:
4
1 2
2 3
4 5
6 7
4
1 5
2 3
4 7
5 7

Output:
2
2
1
1
【分析】某人狩猎，在一条直线上，在时间区间[l,r]上会出现一只猎物，有这样的n个区间。这个人只有一支箭，所以只能射一次，由于所有猎物都在一条直线上，
 所以在同一时刻出现的猎物可以同时被射死。然后给你q次询问，每次 询问给出一个区间，问在此区间内这个人用一支箭最多可以射死多少只猎物。
 这就是个区间覆盖问题，求某一整数点最多覆盖多少区间。这就可以用线段树来做了，几乎模板题。记得离散化。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 100000000
#define met(a,b) memset(a,b,sizeof a)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
using namespace std;
const int N = 4e5+5;
const int M = 4e5+5;
int n,sum[2*N],m;
int lazy[2*N];
int num[N*2];
int ql[N*2],qr[N*2];
map<int,int>mp;
struct man{
    int l,r;
}a[N*2];
void pushup(int pos){
    sum[pos]=max(sum[pos*2],sum[pos*2+1]);
}
void pushdown(int pos){
    if(lazy[pos]){
        lazy[pos*2]+=lazy[pos];lazy[pos*2+1]+=lazy[pos];
        sum[pos*2]+=lazy[pos];
        sum[pos*2+1]+=lazy[pos];
        lazy[pos]=0;
    }return;
}

void update(int L,int R,int val,int l,int r,int pos) {
    if(l>=L&&r<=R) {
        lazy[pos]+=val;
        sum[pos]+=val;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(pos);
    if(L<=mid) update(L,R,val,l,mid,pos<<1);
    if(mid<R)update(L,R,val,mid+1,r,pos<<1|1);
    pushup(pos);
}
int  query(int L,int R,int l,int r,int pos) {
    if(l>=L&&r<=R){
        return sum[pos];
    }
    int mid=(l+r)>>1;
    pushdown(pos);
    int ans=0;
    if(L<=mid) ans=max(query(L,R,l,mid,pos<<1),ans);
    if(R>mid) ans=max(query(L,R,mid+1,r,pos<<1|1),ans);
    return ans;
}
int main() {
    int ll,rr,cnt=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
        num[cnt++]=a[i].l;
        num[cnt++]=a[i].r;
    }
    scanf("%d",&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&ql[i],&qr[i]);
        num[cnt++]=ql[i];
        num[cnt++]=qr[i];
    }
    sort(num,num+cnt);
    int all=0;
    for(int i=0;i<cnt;i++)if(!mp[num[i]])mp[num[i]]=++all;
    for(int i=1;i<=n;i++)update(mp[a[i].l],mp[a[i].r],1,1,all,1);
    for(int i=0;i<m;i++){
        printf("%d
",query(mp[ql[i]],mp[qr[i]],1,all,1));
    }
    return 0;
}