题目描述
给定N个数对(xi, yi)，求最长上升子序列的长度。上升序列定义为{(xi, yi)}满足对i<j有xi<xj且yi<yj。
样例输入
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
样例输出
3
题解
CDQ分治+树状数组
一道经典的二维偏序问题。
由于限制条件有2维，所以我们可以使用CDQ分治处理第一维，用树状数组维护第二维。
具体地，按照CDQ分治的思路，先处理左半部分的答案，再处理左边对右边的影响，最后再处理右半部分的答案。
处理左边对右边的影响时，先按照第一维排序，每次比较左右的第一维大小，若左半部分较小则把答案加入到树状数组中，若右半部分较小则把使用树状数组求出前缀最大值。
然后由于还要处理右半部分，所以还要按照原顺序排回来。树状数组需要清空，但不能使用memset，详见代码。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
struct data
{
int p , x , y , dp;
}a[N];
int n , f[N] , v[N];
bool cmp1(data a , data b)
{
return a.x < b.x;
}
bool cmp2(data a , data b)
{
return a.p < b.p;
}
void add(int x , int a)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] = max(f[i] , a);
}
int query(int x)
{
int i , ans = 0;
for(i = x ; i ; i -= i & -i) ans = max(ans , f[i]);
return ans;
}
void clear(int x)
{
int i;
for(i = x ; i <= n ; i += i & -i) f[i] = 0;
}
void solve(int l , int r)
{
if(l >= r) return;
int mid = (l + r) >> 1 , p1 = l , p2 = mid + 1 , i;
solve(l , mid) , sort(a + l , a + mid + 1 , cmp1) , sort(a + mid + 1 , a + r + 1 , cmp1);
while(p2 <= r)
{
if(p1 <= mid && a[p1].x < a[p2].x) add(a[p1].y , a[p1].dp) , p1 ++ ;
else a[p2].dp = max(a[p2].dp , query(a[p2].y - 1) + 1) , p2 ++ ;
}
for(i = l ; i <= mid ; i ++ ) clear(a[i].y);
sort(a + mid + 1 , a + r + 1 , cmp2) , solve(mid + 1 , r);
}
int main()
{
int i , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d%d" , &a[i].x , &a[i].y) , a[i].p = i , v[i] = a[i].y , a[i].dp = 1;
sort(v + 1 , v + n + 1);
for(i = 1 ; i <= n ; i ++ ) a[i].y = lower_bound(v + 1 , v + n + 1 , a[i].y) - v;
solve(1 , n);
for(i = 1 ; i <= n ; i ++ ) ans = max(ans , a[i].dp);
printf("%d\n" , ans);
return 0;
}