bzoj 2225 [Spoj 2371]Another Longest Increasing

这道题连续上升的三元组且已经按照第一维排好序了。

直接上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即可。

巴特西

bzoj 2225 [Spoj 2371]Another Longest Increasing

最新文章

热门文章