#P1852. [MexicoOI06]最长不下降序列

    ID: 874 传统题 1000ms 64MiB 尝试: 122 已通过: 29 难度: 7 上传者: 标签>CF2300提高+/省选-自定义排序规则交换论证线性 DP离散化懒标记线段树

[MexicoOI06]最长不下降序列

题目描述

给你 nn 对数 a1,b1…,an,bna_1,b_1\dots,a_n,b_n。要求你从中找出最多的对,把它们按照一种方式排列,重新标号 1,2,…,k1,2,\dots,k。能满足对于每一对 i<ji<j,都有 ai>bja_i>b_j。

输入格式

第一行给出一个数字 nn。

下面 nn 行,分别给出 ai,bia_i,b_i。

输出格式

输出 kk 的极大值。

样例

4
3 12
10 20
21 13
10 2
3

数据规模与约定

对于 100%100\% 的数据,保证 n≤105n\le 10^5,ai,bi≤109a_i,b_i\le 10^9。