区间 (Standard IO)

题意/Description:

       Alice收到一些很特别的生日礼物：区间。即使很无聊，Alice还是能想出关于区间的很多游戏，其中一个是，Alice从中选出最长的不同区间的序列，其中满足每个区间必须在礼物中，另序列中每个区间必须包含下一个区间。
　　编程计算最长序列的长度。

 

读入/Input：

       输入文件第一行包含一个整数N(1<=N<=100000)，表示区间的个数。
　　接下来N行，每行两个整数A和B描述一个区间(1<=A<=B<=1000000)。

 

输出/Output：

       输出满足条件的序列的最大长度。

 

题解/solution：

       多关键字排序，从小到大排x，x相等排y，y大到小。然后DP就OK了。详情见程序。

       本以为c++自带sort，开开心心的写完。发现c++sort不能多关键字排序，卡了半个小时，注意点。

 

代码/Code：

#include <stdio.h>    
#include <iostream>    
#include <algorithm>    
#include <sstream>    
#include <stdlib.h>    
#include <string.h>    
#include <limits.h>    
#include <string>    
#include <time.h>    
#include <math.h>    
#include <queue>    
#include <stack>    
#include <map>    
using namespace std;
struct arr{
	int x,y;
}tu[100001];
int ans,n;
int ma[100001];
int qsort(int l,int r){
	int miy,i,j,mid,t;
    i=l; j=r;
    mid=tu[(l+r)/2].x;
    miy=tu[(l+r)/2].y;
    do
    {
		while ((tu[i].x<mid)||(tu[i].x==mid)&&(tu[i].y>miy)) ++i;
      	while ((tu[j].x>mid)||(tu[j].x==mid)&&(tu[j].y<miy)) --j;
      	if (i<=j){
			t=tu[i].x; tu[i].x=tu[j].x; tu[j].x=t;
			t=tu[i].y; tu[i].y=tu[j].y; tu[j].y=t;      	
        	i+=1; j-=1;
        }
     }
    while (i<=j);
    if (l<j) qsort(l,j);
    if (i<r) qsort(i,r);
}

int find(int o,int p,int v){
	int mid;
  	while (o<=p) { 
    	mid=o+(p-o)/2;
    	if (ma[mid]>=v) o=mid+1; else p=mid-1;
	}
	return o;
}

int main(){
	scanf("%ld",&n);
	for (int i=1;i<=n;i++)
		scanf("%ld%ld",&tu[i].x,&tu[i].y);
	qsort(1,n);
	ans=0; 
  	for (int i=1;i<=n;i++){
    	int j=find(1,i,tu[i].y);
    	if (tu[i].y>ma[j]) ma[j]=tu[i].y;
    	if (j>ans) ans=j;
	}
	printf("%ld",ans);
}