题意:
给出n个二维点对,求LIS长度和编号字典序最小的LIS(x非增,y非减)
题解:
dp[i]=max(dp[j]) (i>j,l[i]>=l[j],r[i]<=r[i])
一看就是三维偏序问题。
如果树套树写的好,空间开的大的话,一样可以过,不过这里还是用cdq分治套树状数组好写一点。
用lowbit来维护dp[j]的最大值,然后因为要字典序最小,所以从后往前dp。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int N=1e5+; int n,dp[N],hsh[N],ed,pre[N]; struct BIT
{
int val,idx;
BIT(){val=,idx=N;}
}bit[N],tp; inline void up(BIT &a,BIT b){if(a.val<b.val||a.val==b.val&&a.idx>b.idx)a=b;}
inline void add(int x,BIT c){while(x<=n)up(bit[x],c),x+=x&-x;}
inline void clr(int x){while(x<=n)bit[x].val=,bit[x].idx=N,x+=x&-x;}
inline BIT ask(int x){BIT ans;while(x)up(ans,bit[x]),x-=x&-x;return ans;} struct node
{
int x,y,idx;
bool operator<(const node & b)const
{
if(y!=b.y)return y<b.y;
if(x!=b.x)return x>b.x;
return idx<b.idx;
}
}a[N],tmp[N]; void cdq(int l,int r)
{
if(l==r)return;
int m=l+r>>;
cdq(m+,r);
F(i,l,r)tmp[i]=a[i];
sort(tmp+l,tmp+m+);
sort(tmp+m+,tmp+r+);
int j=r;
for(int i=m;i>=l;i--)
{
for(;j>m&&tmp[j].y>=tmp[i].y;j--)
{
tp.val=dp[tmp[j].idx],tp.idx=tmp[j].idx;
add(tmp[j].x,tp);
}
BIT an=ask(tmp[i].x);
if(dp[tmp[i].idx]<an.val+)dp[tmp[i].idx]=an.val+,pre[tmp[i].idx]=an.idx;
else if(dp[tmp[i].idx]==an.val+)pre[tmp[i].idx]=min(pre[tmp[i].idx],an.idx);
}
F(i,m+,r)clr(tmp[i].x);
cdq(l,m);
} int main()
{
while(~scanf("%d",&n))
{
F(i,,n)scanf("%d",&a[i].x),a[i].idx=i,dp[i]=,pre[i]=N;
F(i,,n)scanf("%d",&a[i].y);
F(i,,n)hsh[i]=a[i].x;
sort(hsh+,hsh++n),ed=unique(hsh+,hsh++n)-hsh;
F(i,,n)a[i].x=lower_bound(hsh+,hsh++ed,a[i].x)-hsh;
F(i,,n)hsh[i]=a[i].y;
sort(hsh+,hsh++n),ed=unique(hsh+,hsh++n)-hsh;
F(i,,n)a[i].y=lower_bound(hsh+,hsh++ed,a[i].y)-hsh;
cdq(,n);
int mx=,st;
F(i,,n)mx=max(mx,dp[i]);
F(i,,n)if(mx==dp[i]){st=i;break;}
printf("%d\n",mx);
for(int i=st,cnt=;i<=n;i=pre[i])printf("%d%c",i," \n"[++cnt==mx]);
}
return ;
}