偏序(cdq bitset)

题目链接:三维偏序

cdq分治:

int k,c[__];

void update(int wz,int val)
{
    for(; wz<=k; wz+=wz&(-wz))
        c[wz]+=val;
}

int get_sum(int wz)
{
    int res=0;
    for(; wz; wz-=wz&(-wz))
        res+=c[wz];
    return res;
}

struct node
{
    int x,y,z,ans,id;
    bool operator==(const node& b)
    {
        if(x==b.x && y==b.y && z==b.z)
            return true;
        return false;
    }
} a[__],t[__];

bool cmp(const node& x,const node& y)
{
    if(x.x!=y.x)return x.x<y.x;
    if(x.y!=y.y)return x.y<y.y;
    if(x.z!=y.z)return x.z<y.z;
    return x.ans>y.ans;
}

void cdq(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1,x=l,y=l;
    cdq(l,mid),cdq(mid+1,r);
    for(int i=mid+1; i<=r; i++)
    {
        while(x<=mid && a[x].y<=a[i].y)
            update(a[x].z,1),t[y++]=a[x++];
        a[i].ans+=get_sum(a[i].z);
        t[y++]=a[i];
    }
    for(int i=x;i<=mid;i++)t[y++]=a[i];
    while(--x>=l)update(a[x].z,-1);
    for(int i=l; i<=r; i++)a[i]=t[i];
}

int ans[__];

int main()
{
    int _;
    scanf("%d",&_);
    while(_--)
    {
        k=0,memset(a,0,sizeof(a));
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
            a[i].id=i;
            if(a[i].z>k)k=a[i].z;
        }
        sort(a+1,a+1+n,cmp);
        cdq(1,n);
        sort(a+1,a+1+n,cmp);
        for(int i=1; i<=n; i++)
            if(i!=1 && a[i]==a[i-1])
                ans[a[i].id]=ans[a[i-1].id];
            else ans[a[i].id]=a[i].ans;
        for(int i=1; i<=n; i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}

题目链接:五维偏序

int a[__][6],rk[6][__];
bitset<__>B[6][__];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=5; ++j)
        {
            scanf("%d",&a[i][j]);
            rk[j][a[i][j]]=i;
        }
    for(int i=1; i<=5; ++i)
        for(int j=2; j<=n; ++j)
        {
            B[i][j]|=B[i][j-1];
            B[i][j].set(rk[i][j-1]-1);
        }
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=5; ++j)
            B[1][a[i][1]]=B[j][a[i][j]]&B[1][a[i][1]];
        printf("%d\n",B[1][a[i][1]].count());
    }
    return 0;
}