HDU 1025 Constructing Roads In JGShining's Kingdom

http://acm.hdu.edu.cn/showproblem.php?pid=1025

题目有一定迷惑性，实际就是求LIS，我原来掌握的朴实的O(n^2)算法果断超时，新学了一种二分dp O(nlog(n))的算法，直接上模板了，还要多多体会啊

#include <iostream>
using namespace std ;
int dp[10001],p[50001];
int LIS(int n)
{
    int l,r,m,i,tail = 0;
    for ( dp[ ++ tail ] = p[ 1 ],i = 2 ; i <= n ; ++ i ) 
    {
        if ( dp[ tail ] <= p[ i ] ) 
        {
            dp[ ++ tail ] = p[ i ];
            continue;
        }
        for ( m=((r=tail)+(l=1)>>1) ; l < r ; m=(l+r)>>1 )
            if ( dp[ m ] <= p[ i ] ) l = m+1;
            else r = m;
        dp[ m ] = p[ i ];
    }
    return tail;
}
inline bool scan_d(int &num) 
{
        char in;bool IsN=false;
        in=getchar();
        if(in==EOF) return false;
        while(in!='-'&&(in<'0'||in>'9')) in=getchar();
        if(in=='-'){ IsN=true;num=0;}
        else num=in-'0';
        while(in=getchar(),in>='0'&&in<='9'){
                num*=10,num+=in-'0';
        }
        if(IsN) num=-num;
        return true;
}
int main()
{
    int n,nCase=1;
    while(scan_d(n))
    {
        for(int i=0;i<n;i++)
        {
            int x,y;
            scan_d(x);
            scan_d(y); 
            p[x]=y;
        }
        int ans=LIS(n);
        printf("Case %d:\n",nCase++);
        if(ans==1)
            puts("My king, at most 1 road can be built.");
        else
            printf("My king, at most %d roads can be built.\n",ans);
        putchar('\n');
    }
    return 0;
}