三维偏序-二维LIS

Another Longest Increasing Subsequence Problem

有两种思路。

思路一：

考虑到如果只有一维，那么可以用f[s]表示长度为s时，最后一个数是多少，把这个想法拓展到二维，即f[s]表示长度为s时，最后一个点的集合，也就是说有多个点，但是这多个点是有顺序，x递增，y递减，并且每次加点进来的时候，随时保持这个顺序。

关于怎么处理点的集合，可以用平衡树来实现，这里用map来代替，而且map自带二分查找的功能。

算法实现：采用二分答案的方法，初始区间是(0,ans)这是刚好合适的情况，每次二分的时候，要验证两个值mid和mid+1，如果只验证mid，成立的时候跳向(mid+1,r)，但是这个区间上可能找不到答案，这和二分查找不一样，这是找最优解，而不是验证存不存在，所以至少要保证mid+1成立才能考查右区间。

最后更新的时候，记住保持x递增，y递减的顺序就可以了，情况比较多，很繁琐，我在这里错了很久，注意边界处的细节怎么处理，详细的看代码。

代码如下：

#include<bits/stdc++.h>

#define rep(i,n) for(i=1;i<=n;i++)

#define F first

#define S second

using namespace std;

const int maxn=100100;

map<int,int>f[maxn];

int n;

int find(int x,int y,int l,int r)

{

	if(l==r)return l;

	int mid=(l+r)>>1;

	map<int,int>::iterator it1,it2;

	it1=f[mid].lower_bound(x);

	it2=f[mid+1].lower_bound(x);

	if(it1==f[mid].begin() || it2==f[mid+1].begin())return find(x,y,l,mid);

	--it1,--it2;

	if(it1->S>=y || it2->S>=y)return find(x,y,l,mid);

	return find(x,y,mid+1,r);

}

void update(int x,int y,int p)

{

	map<int,int>::iterator it1=f[p].lower_bound(x),it2=it1;

	if(it1!=f[p].end() && it1->F == x && it1->S<=y)return ;

	if(it1!=f[p].begin() && (--it1)->S<=y)return ;

	while(it2!=f[p].end() && it2->S>=y)f[p].erase(it2++);

	f[p][x]=y;

}

int main()

{

	int i,ans=0;

	scanf("%d",&n);

	f[0][-2000000000]=-2000000000;

	rep(i,n)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		int pos=find(x,y,0,ans);

		ans=max(ans,++pos);

		update(x,y,pos);

	}

	printf("%d",ans);

}

　　方法二：CDQ分治。

采用分治的思想，先处理左区间，再用左区间更新一次右区间，再处理右区间，这样就保证每次处理的时候都是用前面的更新过的。

一共有三维的坐标x:点的下标，y:点的横坐标，z:点的纵坐标。分治的时候，因为是用左区间来更新右区间，所以x保证是升序的，可以左右区间分别将y排序，每次更新右区间的时候，都依次遍历看哪些左区间的点可以加进去，可以用数据结构进行转移（线段树，树状数组都可以，只是线段树在本题中会超时），将离散化后的z坐标作为下标，f[x]作为值对数组数组（或线段树）进行更新，查询符合条件的f 最大值。每次转移完成后，要把线段树或树状数组清空，不要用memset，更新了哪些就清空哪些。最后还要将区间上的点按x的顺序重新排好序，保证接下来处理的时候x是升序的。

注意：sort（a+st,a+ed,cmp)实际上是对(a[st],a[ed-1])之间的元素进行排序！

代码如下（线段树）：

#include<bits/stdc++.h>

#define rep(i,n) for(i=1;i<=n;i++)

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

using namespace std;

const int maxn=100100;

int tree[maxn*4],f[maxn],a[maxn];

struct zz{int x,y,z;}poi[maxn];

int n;

bool cmpy(const zz& i,const zz&j)

{

	return i.y<j.y;

}

bool cmpx(const zz&i,const zz&j)

{

	return i.x<j.x;

}

int find(int v,int l,int r)

{

	int mid=(l+r)>>1;

	if(l==r)return l;

	if(v<=a[mid])return find(v,l,mid);

	return find(v,mid+1,r);

}

void update(int p,int add,int l,int r,int rt)

{

	if(l==r)

	{

		tree[rt]=(add==0?add:max(tree[rt],add));

		return ;

	}

	int mid=(l+r)>>1;

	if(p<=mid)update(p,add,lson);

	else update(p,add,rson);

	tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);

}

int query(int L,int R,int l,int r,int rt)

{

	if(L>R)return 0;

	if(l>=L && r<=R)return tree[rt];

	int mid=(l+r)>>1;

	if(mid>=R)return query(L,R,lson);

	if(mid<L)return query(L,R,rson);

	return max(query(L,R,lson),query(L,R,rson));

}

void work(int l,int r)

{

	int mid=(l+r)>>1;

	sort(poi+l,poi+mid+1,cmpy);

	sort(poi+mid+1,poi+r+1,cmpy);

	for(int i=l,j=mid+1;j<=r;j++)

	{

		while(poi[i].y<poi[j].y && i<=mid)

		{

			update(poi[i].z,f[poi[i].x],1,n,1);

			i++;

		}

		f[poi[j].x]=max(f[poi[j].x],query(1,poi[j].z-1,1,n,1)+1);

	}

	for(int i=l;i<=mid;i++)update(poi[i].z,0,1,n,1);

	sort(poi+mid+1,poi+r+1,cmpx);

}

void CDQ(int l,int r)

{

	int mid=(l+r)>>1;

	if(l==r)return;

	CDQ(l,mid);

	work(l,r);

	CDQ(mid+1,r);

}

int main()

{

	// freopen("D.in","r",stdin);

	// freopen("D.out","w",stdout);

//	ios::sync_with_stdio(false);

	//cin>>n;

	scanf("%d",&n);

	int i;

	rep(i,n)

	{

	//	cin>>poi[i].y>>poi[i].z;

		scanf("%d%d",&poi[i].y,&poi[i].z);

		a[i]=poi[i].z;

		poi[i].x=i;

		f[i]=1;

	}

	sort(a+1,a+n+1);

	rep(i,n)poi[i].z=find(poi[i].z,1,n);

	//rep(i,n)cout<<poi[i].z<<endl;

	CDQ(1,n);

	int ans=0;

	rep(i,n) ans=max(ans,f[i]);

//	rep(i,n)cout<<f[i]<<endl;

	//ios::sync_with_stdio(true);

//	cout<<ans<<endl;

	printf("%d",ans);

	return 0;

}

巴特西

三维偏序-二维LIS

最新文章

热门文章