#P2225. [Spoj 2371]Another Longest Increasing

    ID: 1250 传统题 1000ms 259MiB 尝试: 446 已通过: 119 难度: 6 上传者: 标签>CF2100提高线性 DP二维树状数组离散化离线预收集坐标局部离散化二分查找

[Spoj 2371]Another Longest Increasing

题目描述

给定 NN 个数对 (xi,yi)(x_i, y_i),求最长上升子序列的长度。上升序列定义为 {(xi,yi)}\{(x_i, y_i)\} 满足对 i<ji\lt j 有 xi<xjx_i\lt x_j 且 yi<yjy_i\lt y_j。

输入格式

第一行一个整数 nn,接下来 nn 行,每行两个整数 xi,yix_i,y_i。

输出格式

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

提示

2≤n≤105,−109≤xi,yi≤1092\le n \le 10^5,-10^9\le x_i,y_i\le 10^9

题目来源

没有写明来源