这道题 连续上升的三元组 且已经按照第一维排好序了。
直接上CDQ分治即可 当然也是可以2-Dtree解决这个 问题 但是感觉nlog^2 比nsqrt(n)要快一些。。
算是复习一发CDQ分治吧 也好久没写了。
原来最长三元上升序列 不是裸的CDQ分治。。我以为是 没细想 最后还是细想了一下实现方式。
首先CDQ左边 然后对于右边此时x是无序的 考虑排序 在外面排序没用好吧。。
好吧可能有用但是太过繁琐那种写法 这里推荐暴力sort。。归并没用 因为归并此时复杂度还是nlogn的。
统计完左边对右边的贡献后 再桶排序复原。再CDQ右边 回来的时候可以进行归并不需要再sort了节省常数。。
复杂度nlog^2。
const int MAXN=100010;
int n,top,ans;
struct wy
{
int x,y;
int id;
inline int friend operator <(wy a,wy b){return a.x==b.x?a.id<b.id:a.x<b.x;}
}t[MAXN],ql[MAXN];
int b[MAXN],f[MAXN],c[MAXN];
inline void discrete()
{
sort(b+1,b+1+n);
rep(1,n,i)if(i==1||b[i]!=b[i-1])b[++top]=b[i];
rep(1,n,i)y(i)=lower_bound(b+1,b+1+top,y(i))-b;
}
inline void add(int x,int y)
{
if(y==-1)
{
while(x<=top)
{
c[x]=0;
x+=x&(-x);
}
return;
}
while(x<=top)
{
c[x]=max(c[x],y);
x+=x&(-x);
}
}
inline int ask(int x)
{
int cnt=0;
while(x)
{
cnt=max(cnt,c[x]);
x-=x&(-x);
}
return cnt;
}
inline void CDQ(int l,int r)
{
if(l==r){++f[id(l)];return;}
int mid=(l+r)>>1;
CDQ(l,mid);
sort(t+mid+1,t+r+1);
int i=l,j=mid+1;
for(int k=l;k<=r+1;++k)
{
if(j>r)
{
for(int w=i-1;w>=l;--w)add(y(w),-1);
break;
}
if((i<=mid)&&x(i)<x(j))add(y(i),f[id(i)]),++i;
else f[id(j)]=max(f[id(j)],ask(y(j)-1)),++j;
}
for(int k=mid+1;k<=r;++k)ql[id(k)]=t[k];
for(int k=mid+1;k<=r;++k)t[k]=ql[k];
CDQ(mid+1,r);
i=l;j=mid+1;
for(int k=l;k<=r;++k)
{
if(i<=mid&&x(i)<x(j)||j>r)ql[k]=t[i],++i;
else ql[k]=t[j],++j;
}
for(int k=l;k<=r;++k)t[k]=ql[k];
}
int main()
{
freopen("1.in","r",stdin);
get(n);
rep(1,n,i)get(x(i)),b[i]=get(y(i)),id(i)=i;
discrete();
CDQ(1,n);
for(int i=1;i<=n;++i)ans=max(ans,f[i]);
printf("%d\n",ans);
return 0;
}
这个树状数组清空的时候注意不要暴力清空 再来一遍序列 清成0即可。