Another Longest Increasing Subsequence Problem
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19929
Description
Given a sequence of N pairs of integers, find the length of the longest increasing subsequence of it.
An increasing sequence A1..An is a sequence such that for every i < j, Ai < Aj.
A subsequence of a sequence is a sequence that appears in the same relative order, but not necessarily contiguous.
A pair of integers (x1, y1) is less than (x2, y2) iff x1 < x2 and y1 < y2.
Input
The first line of input contains an integer N (2 ≤ N ≤ 100000).
The following N lines consist of N pairs of integers (xi, yi) (-109 ≤ xi, yi ≤ 109).
Output
The output contains an integer: the length of the longest increasing subsequence of the given sequence.
Sample Input
8
1 3
3 2
1 1
4 5
6 3
9 9
8 7
7 6
Sample Output
3
HINT
题意
求三维偏序最长链
题解：
CDQ分治
树套树会TLE（反正我的会TLE。。。。
代码：
#include<iostream>
#include<stdio.h>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = +;
inline long long read()
{
long long x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
struct node
{
int x,y,z;
}p[maxn];
int n;
map<int,int> H;
vector<int> Q;
void Li()
{
for(int i=;i<=n;i++)
Q.push_back(p[i].z);
sort(Q.begin(),Q.end());
for(int i=;i<=n;i++)
p[i].z=lower_bound(Q.begin(),Q.end(),p[i].z)-Q.begin()+;
}
bool cmpx(node A,node B)
{
return A.x<B.x;
}
bool cmpy(node A,node B)
{
return A.y<B.y;
}
int dp[maxn];
int d[maxn];
int lowbit(int x)
{
return x&(-x);
}
void updata(int x,int val)
{
for(int i=x;i<n+;i+=lowbit(i))
d[i]=max(d[i],val);
}
int query(int x)
{
int res = ;
for(int i=x;i;i-=lowbit(i))
res=max(res,d[i]);
return res;
}
void init(int x)
{
for(int i=x;i<n+;i+=lowbit(i))
d[i]=;
}
void solve(int L,int R){
int m=(L+R)>>;
sort(p+L,p+m+,cmpy);
sort(p+m+,p+R+,cmpy);
int j=L;
for(int i=m+;i<=R;i++){
for(;j<=m&&p[j].y<p[i].y;j++)
updata(p[j].z,dp[p[j].x]);
int tmp=query(p[i].z-)+;
dp[p[i].x]=max(dp[p[i].x],tmp);
}
for(int i=L;i<=m;i++)init(p[i].z);
sort(p+m+,p+R+,cmpx);
} void CDQ(int L,int R){
if(L==R)return;
int m=(L+R)>>;
CDQ(L,m);
solve(L,R);
CDQ(m+,R);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
p[i].y=read(),p[i].z=read();
p[i].x = i;
dp[i]=;
}
Li();
CDQ(,n);
int Ans = ;
for(int i=;i<=n;i++)
Ans=max(Ans,dp[i]);
printf("%d\n",Ans);
}