三维偏序-二维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;
}

原文链接: https://www.cnblogs.com/xionglinlin/p/5030765.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍