首页 > ACM题库 > HDU-杭电 > HDU 4343-Interval query-排序-[解题报告]HOJ
2015
05-23

HDU 4343-Interval query-排序-[解题报告]HOJ

Interval query

问题描述 :

This is a very simple question. There are N intervals in number axis, and M queries just like “QUERY(a,b)” indicate asking the maximum number of the disjoint intervals between (a,b) .

输入:

There are several test cases. For each test case, the first line contains two integers N, M (0<N, M<=100000) as described above. In each following N lines, there are two integers indicate two endpoints of the i-th interval. Then come M lines and each line contains two integers indicating the endpoints of the i-th query.
You can assume the left-endpoint is strictly less than the right-endpoint in each given interval and query and all these endpoints are between 0 and 1,000,000,000.

输出:

There are several test cases. For each test case, the first line contains two integers N, M (0<N, M<=100000) as described above. In each following N lines, there are two integers indicate two endpoints of the i-th interval. Then come M lines and each line contains two integers indicating the endpoints of the i-th query.
You can assume the left-endpoint is strictly less than the right-endpoint in each given interval and query and all these endpoints are between 0 and 1,000,000,000.

样例输入:

3 2
1 2
2 3
1 3
1 2
1 3

样例输出:

1
2

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4343

题目大意:给定N(N<=100000)个区间(左闭右开)和M(M<=100000)个询问[l, r],问所有满足[s,t)包含于于[l, r]的区间中最多能选出多少个,使得他们两两不相交。

解题思路:首先将坐标离散化,将区间排序后删掉可以覆盖其他区间的大区间。
这时若将剩余区间的左端点坐标排序,左端点坐标必然严格上升且对应的右端点坐标也是严格上升的。
此题的贪心思想较为普及,即按y的升序进行贪心固定区间询问的最大数量,不再赘述。
设g[1][x]为从坐标x开始向右遇到的第一个有效区间的右端点坐标,另g[i][x] = g[1][g[i-1][x]],若不存在则为正无穷。
则g[k][x]表示从坐标x开始,在经过不相交的k个区间后,第k个区间的右端点的坐标。
对g进行倍增,即设f[k][x] = g[2^k][x]。则对于一次询问(l,r),可利用f枚举答案各个二进制数位得到答案。
f[k][x] = f[k-1][f[k-1][x]],f[0][x] = g[1][x]。g只存在于思维过程中。

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=100050;
int n,m,opt[20][N*2],x[N*2],cnt;
struct node
{
    int l,r;
    void read(){ scanf("%d%d",&l,&r); x[cnt++]=l; x[cnt++]=r; }
    void print(){ printf("%d %d\n",l,r); }
    bool operator <(const node tmp) const{ return l<tmp.l||(l==tmp.l&&r<tmp.r); }
}no[N];
inline int getid(int val,bool f)
{
    if(!f) return lower_bound(x,x+cnt,val)-x;
    return upper_bound(x,x+cnt,val)-x-1;
}
int calc(int l,int r)
{
    if(l>r) return 0;
    if(l==cnt||r==-1) return 0;
    int ret=0;
    for(int i=19;i>=0;i--){
        if(opt[i][l]<=r) {
            ret+=(1<<i);
            l=opt[i][l];
        }
    }
    return ret;
}
int main()
{
//    freopen("1.in","r",stdin);
//    freopen("2.out","w",stdout);
    while(scanf("%d%d",&n,&m)!=-1)
    {
        cnt=0;
        for(int i=0;i<n;i++){
            no[i].read();
        }
        sort(no,no+n);
        sort(x,x+cnt);
        cnt=unique(x,x+cnt)-x;
        for(int i=0;i<n;i++){
            no[i].l=getid(no[i].l,0);
            no[i].r=getid(no[i].r,1);
        }
        x[cnt]=cnt;
        int mn=cnt,r=n;
        for(int i=cnt-1;i>=0;i--)
        {
            while(r>0&&no[r-1].l>=i){
                r--;
                mn=min(mn,no[r].r);
            }
            opt[0][i]=mn;
        }
        for(int i=0;i<20;i++) opt[i][cnt]=cnt;
        for(int i=1;i<20;i++){
            for(int j=0;j<cnt;j++){
                opt[i][j]=opt[i-1][opt[i-1][j]];
            }
        }
        while(m--)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            l=getid(l,0); r=getid(r,1);
            printf("%d\n",calc(l,r));
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/longshuai0821/article/details/7845112