[文章目录]
Description
给定N个数对(xi, yi)，求最长上升子序列的长度。上升序列定义为{(xi, yi)}满足对i<j有xi<xj且yi<yj。n<=100000
终于知道什么叫做CDQ分治了。
具有分治思想，可以消除一维树结构。
CDQ的思想就是先处理左区间，然后处理左区间对右区间的影响，再处理右区间。
假设这个操作是O(n)的，那么则有T(n)=2*T(n/2)+O(n),递推式推一下发现是O()的，同理如果这个操作是O()的，总时间复杂度是O(n)的。如果是O()，那么总时间复杂度是O()。看着好像都很优越。
注意，其中每个操作的时间复杂度只跟当前处理区间的长度有关，如果跟整个区间长度有关，时间复杂度是不对的。
CDQ分治对于每个区间的处理原则是前面区间对当前区间的影响已经处理完了，来达到当前区间可以单独处理的效果。
那么对于一个不用考虑前面区间影响的区间，进行分治，区间分成两半，左区间和原问题一样，递归进行处理，然后处理左区间对右区间的影响。然后处理右区间。
对于这道题，将序列进行CDQ分治，求出以每个元素结尾的上升序列。
发现左区间的处理和问题一样，不用考虑。那么问题在于处理左区间对右区间的影响上。如果想单独考虑右区间解决问题，只能将右区间的每个元素的初始身价先统计出来。
将序列按x递增排序，从头至尾扫，每扫到一个左区间元素，通过权值树状数组维护其y值与其长度，对于右区间元素，查询y值比其大的最长长度来更新身价。时间复杂度O()
所以总时间复杂度O()。
树状数组清空的时候不能用memset，因为memset跟序列长度有关，而不是区间长度，时间复杂度不对。那么只能再跑一遍来清零。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,f[101000],b[101000],c[101000],dp[101000],tot,ans;
int getid(int x)
{
int l=1,r=tot+1,mid;
while(l<r) {mid=l+r>>1; (c[mid]>=x)?r=mid:l=mid+1;}
return r;
}
struct node
{
int x,y,id;
}a[101000];
bool cmp(node x,node y)
{
return x.x==y.x?(x.y==y.y ? x.id<y.id : x.y<y.y):x.x<y.x;
}
bool cmp1(node x,node y){return x.id<y.id;}
void fix(int x,int y)
{
while(x<=tot) f[x]=max(f[x],y),x+=-x&x;
}
void clear(int x){while(x<=tot) f[x]=0,x+=-x&x;}
int query(int x)
{
int re=0;
while(x>0) re=max(re,f[x]),x-=-x&x;
return re;
}
void solve(int l,int r)
{
if(l==r) {dp[l]=max(dp[l],1); return ;}
int mid=l+r>>1;
solve(l,mid); sort(a+l,a+r+1,cmp);
int i;
for(i=l;i<=r;++i)
{
if(a[i].id<=mid) fix(getid(a[i].y),dp[a[i].id]);
else dp[a[i].id]=max(dp[a[i].id],query(getid(a[i].y)-1)+1);
}
for(i=l;i<=r;++i)
if(a[i].id<=mid) clear(getid(a[i].y));
sort(a+l,a+r+1,cmp1);
solve(mid+1,r);
}
int main()
{
scanf("%d",&n); int i;
for(i=1;i<=n;++i)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id=i;
b[i]=a[i].y;
}
sort(b+1,b+n+1);
c[1]=b[1]; tot=1;
for(i=2;i<=n;++i)
if(b[i]!=b[i-1]) c[++tot]=b[i];
solve(1,n);
for(i=1;i<=n;++i) ans=max(ans,dp[i]);
printf("%d\n",ans);
return 0;
}