题目描述
给定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; }