BZOJ-2253: [2010 Beijing wc]纸箱堆叠

[文章目录]

Description

求最长三维严格LIS的长度,即对于答案有a[i] < a[i+1],b[i] < b[i+1],c[i] < c[i+1]。个数<=50000 a,b,c<=2 * 10^9

改变一下CDQ分治的方式:
对于第一维,由于CDQ的复杂度第一维是只跟分治层数有关的,所以我们可以按照a的种类分治,相同的a看做一组进行分治,保证右区间可以接到左区间元素后面。
对于第二维,归并排序的时候将条件改为b[l] <= b[r]-1 即b[l] < b[r]。转化为<=
对于第三维,直接在树状数组中查询c[i]-1即可。
时间复杂度O(nlog^2n)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,f[51000],lim;
struct node
{
    int a,b,c,dp;
    node(){a=b=c=0; dp=1;}
}a[51000];
bool cmpa(node x,node y){return x.a<y.a;}
bool cmpb(node x,node y){return x.b<y.b;}
bool cmpc(node x,node y){return x.c<y.c;}
inline int Max(int x,int y){return x>y ? x:y;}
inline void fix(int x,int y) {while(x<=lim) f[x]=Max(f[x],y),x+=-x&x;}
inline void clear(int x){while(x<=lim) f[x]=0,x+=-x&x;}
inline int query(int x){int re=0; while(x>0) re=Max(re,f[x]),x-=-x&x; return re;}
void solve(int l,int r)
{
    if(a[l].a==a[r].a) return;
    int mid=(a[l].a+a[r].a)>>1;
    for(int i=l;i<=r;++i) if(a[i].a>mid) {mid=i-1; break;}
    solve(l,mid); sort(a+mid+1,a+r+1,cmpb);
    int t1=l,t2=mid+1;
    for(int i=l;i<=r;++i)
    {
        if(t2>r||(t1<=mid&&a[t1].b<a[t2].b)) fix(a[t1].c,a[t1].dp),t1++;
        else a[t2].dp=Max(a[t2].dp,query(a[t2].c-1)+1),t2++;
    }
    for(int i=l;i<=mid;++i) clear(a[i].c);
    sort(a+mid+1,a+r+1,cmpa); solve(mid+1,r); sort(a+l,a+r+1,cmpb);
}
int main()
{
    ll now=1,w,p;
    scanf("%lld%lld%d",&w,&p,&n);
    for(int i=1;i<=n;++i)
    {
        now=now*w%p; a[i].a=now;
        now=now*w%p; a[i].b=now;
        now=now*w%p; a[i].c=now;
        if(a[i].b>a[i].c) swap(a[i].b,a[i].c);
        if(a[i].a>a[i].b) swap(a[i].a,a[i].b);
        if(a[i].b>a[i].c) swap(a[i].b,a[i].c);
    }
    sort(a+1,a+n+1,cmpb);
    now=a[1].b; a[1].b=1; w=1;
    for(int i=2;i<=n;++i)
        (a[i].b==now) ? a[i].b=w : (now=a[i].b,a[i].b=++w);//问号表达式和逗号表达式一定要加括号。
    sort(a+1,a+n+1,cmpc);
    now=a[1].c; a[1].c=1; w=1;
    for(int i=2;i<=n;++i)
        (a[i].c==now) ? a[i].c=w : (now=a[i].c,a[i].c=++w);
    lim=w;
    sort(a+1,a+n+1,cmpa);
    now=a[1].a; a[1].a=1; w=1;
    for(int i=2;i<=n;++i)
        (a[i].a==now) ? a[i].a=w : (now=a[i].a,a[i].a=++w);
    solve(1,n);
    int ans=0; for(int i=1;i<=n;++i) ans=Max(ans,a[i].dp);
    printf("%d",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注