[BZOJ2253] [2010 Beijing wc] 종이 상자 쌓기(dp+bit+cdq 분리)

제목 설명

컨베이어 도어

풀다

최장 상승 서브 서열 + 3차원 편차 문제 누드 dp 사람마다 맞겠죠 O(n2)는 서열에 대해 cdq분치를 고려합니다. 매번 왼쪽 구간으로 오른쪽 구간을 x분치에 따라 업데이트하고 매번 y분치에 따라 정렬합니다. 그리고 z는 나무 모양 수조로 조회합니다. 주의해야 할 것은 여기는 모두 엄격합니다. 즉, 분치를 할 때 좌우 양쪽으로 구분된 점에서 x가 같지 않은 상황입니다.이렇게 하면 미리 처리한 다음에 선택점을 선택할 때 하면 됩니다. 그리고 갱신 순서는 반드시 왼쪽 구간으로 돌아가야 합니다. 왼쪽 구간이 오른쪽 구간에 미치는 영향을 처리하고 오른쪽 구간으로 돌아가야 합니다.

코드

#include
#include
#include
#include
#include
using namespace std;
#define N 300005

int A,Mod,n,LSH,ans;
int lsh[N],L[N],R[N],C[N],f[N],ch[N];
struct data{int x,y,z,id;}q[N],a[N],b[N];

int cmp(data a,data b)
{
    return a.xx||(a.x==b.x&&a.yy)||(a.x==b.x&&a.y==b.y&&a.zint cmpy(data a,data b)
{
    return a.yy;
}
void cover(int loc)
{
    for (int i=loc;i<=LSH;i+=i&-i)
        C[i]=0;
}
void add(int loc,int val)
{
    for (int i=loc;i<=LSH;i+=i&-i)
        C[i]=max(C[i],val);
}
int query(int loc)
{
    int ans=0;
    for (int i=loc;i>=1;i-=i&-i)
        ans=max(ans,C[i]);
    return ans;
}
void cdq(int l,int r)
{
    if (q[l].x==q[r].x) return;
    int mid=(l+r)>>1;
    if (L[mid]!=l) mid=L[mid]-1;
    else mid=R[mid];
    cdq(l,mid);

    int tot=0;
    int pa=1,pb=1,acnt=0,bcnt=0;
    for (int i=l;i<=mid;++i) a[++acnt]=q[i];
    for (int i=mid+1;i<=r;++i) b[++bcnt]=q[i];
    sort(a+1,a+acnt+1,cmpy);sort(b+1,b+bcnt+1,cmpy);
    while (pb<=bcnt)
    {
        while (pa<=acnt&&a[pa].yy)
        {
            add(a[pa].z,f[a[pa].id]);
            ch[++tot]=a[pa].z;
            ++pa;
        }
        f[b[pb].id]=max(f[b[pb].id],query(b[pb].z-1)+1);
        ++pb;
    }
    for (int i=1;i<=tot;++i) cover(ch[i]);

    cdq(mid+1,r);
}
int main()
{
    scanf("%d%d%d",&A,&Mod,&n);q[0].z=1;
    for (int i=1;i<=n;++i)
    {
        q[i].x=(long long)q[i-1].z*A%Mod,q[i].y=(long long)q[i].x*A%Mod;
        q[i].z=(long long)q[i].y*A%Mod;
        lsh[++LSH]=q[i].x,lsh[++LSH]=q[i].y,lsh[++LSH]=q[i].z;
    }
    for (int i=1;i<=n;++i)
    {
        if (q[i].x>q[i].y) swap(q[i].x,q[i].y); 
        if (q[i].y>q[i].z) swap(q[i].y,q[i].z);
        if (q[i].x>q[i].y) swap(q[i].x,q[i].y);
    }
    sort(lsh+1,lsh+LSH+1);LSH=unique(lsh+1,lsh+LSH+1)-lsh-1;
    for (int i=1;i<=n;++i)
        q[i].x=lower_bound(lsh+1,lsh+LSH+1,q[i].x)-lsh,
        q[i].y=lower_bound(lsh+1,lsh+LSH+1,q[i].y)-lsh,
        q[i].z=lower_bound(lsh+1,lsh+LSH+1,q[i].z)-lsh;
    sort(q+1,q+n+1,cmp);
    for (int i=1;i<=n;++i) q[i].id=i;

    for (int i=1;i<=n;++i)
        if (i==1||q[i].x!=q[i-1].x) L[i]=i;
        else L[i]=L[i-1];
    for (int i=n;i>=1;--i)
        if (i==n||q[i].x!=q[i+1].x) R[i]=i;
        else R[i]=R[i+1];
    f[q[1].id]=1;
    cdq(1,n);
    for (int i=1;i<=n;++i) ans=max(ans,f[i]);
    printf("%d
",ans);
}