P3810 【模板】三维偏序（陌上花开）题解

· · 题解

题目传送门

前言

这是一篇分块题解。

题意

有 n 个元素，每个元素有三个属性，求对于每个元素三个属性都小于等于它的元素个数。

这个题意不好处理，我们可以把它转化一下，先按 a 属性为第一关键字，属性 b 为第二关键字，属性 c 最末排序，问题就转化成了：

有 n 个元素，每个元素有两个属性，求对于每个元素它的前缀中两个元素都小于等于它的元素的个数。

做法

考虑对于序列分块，每处理完一个块，就重构一个数组。

对于每个元素，块内的暴力比较，时间复杂度 O(\sqrt{n}) 。

对于前面的元素，直接从处理出的数组中读出答案，时间复杂度 O(1) 。

考虑怎么处理出一个这样的数组。

将一个元素的两个属性对应到一个二维平面上，可以看出一个元素对后面的元素做贡献，必须要它处于后面元素的右下方。

于是我们可以把每个数加到对应的点上，然后做一遍二维前缀和。

但是这样时间复杂度是 O(n^2) 的，明显会超时，考虑优化。

因为这些前面的元素在这次重构后只用对后一个块中的元素做贡献，所以它们的属性大小不重要，只有与后面这些元素属性的相对大小有意义。

于是把前面的元素属性按与后面这些元素属性的相对大小经行离散化，再做上面的操作，时间复杂度是 O(\max(n,B^2)) 的，在 B 取 \sqrt{n} 时最优。

总共重构 \sqrt{n} 次，总时间复杂度 O(n\sqrt{n}) 。

实现细节

对于重复的元素，他们内部会重复贡献，不好处理，于是把它们删成一个元素，公用这个元素的答案即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
    register int a=0;register char ch=getchar();
    while(ch>'9'||ch<'0'){ch=getchar();}
    while(ch>='0'&&ch<='9'){(a*=10)+=(ch^48);ch=getchar();}
    return a;
}
int n,k,f[100010],p,tot,s[100010],ans[100010],d[100010];
int cl,c[100010],st[400],ed[400],mp[500][500],cb[200010],cc[200010];
struct poit
{
    int a,b,c,id,cnt;
}a[100010];
inline bool cmp(poit x,poit y){return x.a==y.a?(x.b==y.b?x.c<y.c:x.b<y.b):x.a<y.a;}
inline void re(register int h)
{
    memset(mp,0,sizeof(mp));
    int totb=0;
    for(register int i=st[h];i<=ed[h];++i)s[++totb]=a[i].b;
    sort(s+1,s+1+totb);
    totb=unique(s+1,s+1+totb)-s-1;
    p=1;
    for(register int i=1;i<=k;++i)
    {
        if(i>s[p]&&p<=totb)++p;
        cb[i]=p;
    }
    int totc=0;
    for(register int i=st[h];i<=ed[h];++i)s[++totc]=a[i].c;
    sort(s+1,s+1+totc);
    totc=unique(s+1,s+1+totc)-s-1;
    p=1;
    for(register int i=1;i<=k;++i)
    {
        if(i>s[p]&&p<=totc)++p;
        cc[i]=p;
    }
    for(register int i=st[h]-1;i;--i)mp[cb[a[i].b]][cc[a[i].c]]+=a[i].cnt;
    for(register int i=1;i<=totb;++i)
    {
        for(register int j=1;j<=totc;++j)
        {
            mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];
        }
    }
    return ;
}
int main()
{
    n=qread();
    k=qread();
    for(register int i=1;i<=n;++i)
    {
        a[i].a=qread();
        a[i].b=qread();
        a[i].c=qread();
        a[i].id=i;
        a[i].cnt=1;
        f[i]=i;
    }
    sort(a+1,a+1+n,cmp);
    p=0;
    for(register int i=1;i<=n;++i)
    {
        if(a[i].a==a[p].a&&a[i].b==a[p].b&&a[i].c==a[p].c)
        {
            ++tot;
            f[a[i].id]=a[p].id;
            a[i].a=k+1;
            ++a[p].cnt;
        }
        else p=i;
    }
    sort(a+1,a+1+n,cmp);
    n-=tot;
    cl=sqrt(n)+1;
    for(register int i=1;i<=n;++i)
    {
        c[i]=(i-1)/cl+1,ed[c[i]]=i;
        ans[a[i].id]+=a[i].cnt-1;
    }
    for(register int i=n;i;--i)st[c[i]]=i;
    for(register int i=1;i<=c[n];++i)
    {
        re(i);
        for(register int j=st[i];j<=ed[i];++j)
        {
            for(register int k=st[i];k<j;++k)
            {
                if(a[k].a<=a[j].a&&a[k].b<=a[j].b&&a[k].c<=a[j].c)ans[a[j].id]+=a[k].cnt;
            }
            ans[a[j].id]+=mp[cb[a[j].b]][cc[a[j].c]];
        }
    }
    for(register int i=1;i<=n+tot;++i)++d[ans[f[i]]];
    for(register int i=0;i<n+tot;++i)printf("%d\n",d[i]);
    return 0;
}

问题延伸

这种方法可以拓展到高维，只用将二维前缀和变为高维前缀和，调整块长即可。

时间复杂度分析：

设块长为 B，则总共重构 \dfrac{n}{B} 次，每次需要做大小为 B 的 k 维前缀和，以及对 n 个数的离散。

对每个元素的询问，需要 O(B) 的比较和 O(1) 的查询。

总共时间复杂度为 O(nB+\dfrac{n}{B}(B^k+n))。

对于最优块长，O(nB) 忽略不计，取 B^k=n 得到 B=\sqrt[k]{n}。

那么最终时间复杂度约为 O(n^\frac{2k-1}{k})。