BZOJ 2225: [Spoj 2371]Another Longest Increasing CDQ

2225: [Spoj 2371]Another Longest Increasing

Time Limit: 20 Sec  Memory Limit: 259 MB
Submit: 362  Solved: 163
[Submit][Status][Discuss]

Description

       给定N个数对(xi, yi)，求最长上升子序列的长度。上升序列定义为{(xi, yi)}满足对i<j有xi<xj且yi<yj。

Input

Output

Sample Input

8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6

Sample Output

3

HINT

数据范围100000

传送门