分析：
最长不降子序列，n很大o(n^2)肯定超，想到了小明序列那个题用线段树维护前面的最大值即可
该题也可用二分搜索来做。
注意问题输出时的坑，路复数后加s
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <string>
#include <cctype>
#include <complex>
#include <cassert>
#include <utility>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
#define lson l,m,rt<<1
#define pi acos(-1.0)
#define rson m+1,r,rt<<1|1
#define All 1,N,1
#define N 500010
#define read freopen("in.txt", "r", stdin)
const ll INFll = 0x3f3f3f3f3f3f3f3fLL;
const int INF= 0x7ffffff;
const int mod = ;
struct city{
int p,r;
}t[N];
bool cmp(city x,city y){
return x.p<y.p;
}
int maxv[N*],n,dp[N];
void pushup(int rt){
maxv[rt]=max(maxv[rt<<],maxv[rt<<|]);
}
void build(int l,int r,int rt){
maxv[rt]=;
if(l==r){
return;
}
int m=(l+r)>>;
build(lson);
build(rson);
}
void update(int p,int v,int l,int r,int rt){
if(l==r){
maxv[rt]=max(maxv[rt],v);
return;
}
int m=(l+r)>>;
if(p<=m)update(p,v,lson);
else update(p,v,rson);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(L<=l&&R>=r)
return maxv[rt];
int m=(l+r)>>;
int ans=;
if(L<=m)ans=max(ans,query(L,R,lson));
if(R>m)ans=max(ans,query(L,R,rson));
return ans;
}
int main()
{
int ca=;
while(~scanf("%d",&n)){
memset(dp,,sizeof(dp));
for(int i=;i<n;++i)
scanf("%d%d",&t[i].p,&t[i].r);
sort(t,t+n,cmp);
build(,n,);
int maxn=;
for(int i=;i<n;++i){
dp[i]=query(,t[i].r,,n,)+;
maxn=max(maxn,dp[i]);
update(t[i].r,dp[i],,n,);
}
printf("Case %d:\n",++ca);
if(maxn>)
printf("My king, at most %d roads can be built.\n",maxn);
else
printf("My king, at most %d road can be built.\n",maxn);
printf("\n");
}
return ;
}