SPOJ LIS2 (Another Longest Increasing Subsequence Problem) CDQ求三维偏序+离散化+LIS

题意：

给n个点的坐标，求最长上升子序列（两个点之间的大于关系是满足同时x，y坐标都大于）

思路：

加上序号，一个点上有三个信息，那么是一个三维偏序+LIS的问题

使用CDQ分治：一维排序，一维分治，一维树状数组维护

由于这里的序号一定是有序的，那么不用第一维的排序

因为是LIS问题，dp[i]=max(dp[j],dp[i])（j<i）

这里的max用树状数组维护前缀最大值

注意x，y的大小范围，要先离散化x或y，我离散的是y

代码如下

#include<bits/stdc++.h>
#define INF 101000
using namespace std;
struct data{
int x,y,id;
}p[INF]; 
int n,t[INF],cnt,e[INF];
int dp[INF];
bool compid(data A,data B){return A.id<B.id;}  
bool compx(data A,data B){return A.x<B.x;}
int lowbit(int x){return x&(-x);}
void add(int pos,int x)
{
while(pos<n+100)
{
e[pos]=max(e[pos],x);
pos+=lowbit(pos);
}
}
int query(int pos)
{
int anss=-1;
while(pos>0)
{
anss=max(anss,e[pos]);
pos-=lowbit(pos);
}
return anss;
}
void clear(int pos)
{
while(pos<n+100)
{
e[pos]=0;
pos+=lowbit(pos);
}
}
void solve(int l,int r)
{
int mid=l+r>>1;
sort(p+l,p+mid+1,compx);
sort(p+mid+1,p+r+1,compx);
int j=l;
for(int i=mid+1;i<=r;i++)
{
for(;j<=mid&&p[j].x<p[i].x;j++)
add(p[j].y,dp[p[j].id]);
dp[p[i].id]=max(dp[p[i].id],query(p[i].y-1)+1);
}
for(int i=l;i<=mid;i++)clear(p[i].y);
sort(p+mid+1,p+r+1,compid);
}
void CDQ (int l,int r)
{
if(l==r)return;
int mid=l+r>>1;
CDQ(l,mid);
solve(l,r);
CDQ(mid+1,r);
}
vector<int> Q; 
void LISAN()
{
    for(int i=1;i<=n;i++)  
Q.push_back(p[i].y);
    sort(Q.begin(),Q.end());
    for(int i=1;i<=n;i++)
        p[i].y=lower_bound(Q.begin(),Q.end(),p[i].y)-Q.begin()+1;
}
int main()
{
//freopen("in.in","r",stdin);
ios::sync_with_stdio(false);cin.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
p[i].id=i;
dp[i]=1;
}
LISAN();
CDQ(1,n);
int ans=-1;
for(int i=1;i<=n;i++)
ans=max(ans,dp[i]);
cout<<ans;
}