hdu 4343 Interval query

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

题目大意：求区间最多有多少不相交线段。

题目思路：先用倍增思想求出dp[i][j]表示左端点为j的线段个数为1<<i的右端点，再由答案的二进制进行搜索。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110000
int max(int a,int b)
{
    return a>b?a:b;
}
int min(int a,int b)
{
    return a<b?a:b;
}
int dp[22][4*Max];
struct node
{
    int v,id;
    bool operator<(const node a)const
    {
        return v<a.v;
    }
}p[4*Max];
struct nn
{
    int l,r;
    bool operator<(const nn a)const
    {
        if(l==a.l)
            return r>a.r;
        return l<a.l;
    }
}in[10*Max];
int query(int x,int y)
{
    int ans=0;
    int i;
    for(i=20;i>=0;i--)
    {
        if(dp[i][x]<=y)
        {
            x=dp[i][x];
            ans+=(1<<i);
        }
    }
    return ans;
}
int main()
{
    int cnt,i,j,n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=0;
        for(i=0;i<n+m;i++)
        {
            scanf("%d%d",&in[i].l,&in[i].r);
            p[cnt].id=cnt;
            p[cnt++].v=in[i].l;
            p[cnt].id=cnt;
            p[cnt++].v=in[i].r;
        }
        sort(p,p+cnt);
        int change=0;
        if(p[0].id%2==0)
            in[p[0].id/2].l=0;
        else
            in[p[0].id/2].r=0;
        for(i=1;i<cnt;i++)
        {
            if(p[i].v!=p[i-1].v) change++;
            if(p[i].id%2==0) in[p[i].id/2].l=change;
            else in[p[i].id/2].r=change;
        }
        sort(in,in+n);
        cnt=1;
        for(i=1;i<n;i++)
        {
            while(in[i].r<=in[cnt-1].r) cnt--;
            in[cnt++]=in[i];
        }
        j=0;
        for(i=0;i<=change;i++)
        {
            for(;j<cnt;j++)
            {
                if(in[j].l>=i) break;
            }
            if(j<cnt)
                dp[0][i]=in[j].r;
            else
                dp[0][i]=inf;
        }
        for(i=1;i<=20;i++)
            for(j=0;j<=change;j++)
            {
                if(dp[i-1][j]==inf)
                    dp[i][j]=inf;
                else
                    dp[i][j]=dp[i-1][dp[i-1][j]];
            }
        for(i=n;i<n+m;i++)
        {
            int ans=query(in[i].l,in[i].r);
            printf("%d\n",ans);
        }
    }
}