书接上回
一维偏序直接做、二维偏序套线段树或归并排序、三维偏序可以树套树或者 CDQ 套树，那四维偏序呢？可以 CDQ 套树套树。那五维偏序呢？可以发现，无论是 CDQ 分治还是树，都很难再继续嵌套，再写下去不但码量巨大，还巨难调，效率还相当低。树或 CDQ 嵌套 \(m\) 维偏序时间复杂度为 \(O(n\log^{m-1}n)\)。但是，我们使用 STL 的 bitset 可以在 \(O(\tfrac{n^2m}{w})\) 的优秀复杂度内解决这个问题。
前置知识：
bitset 的基本用法
最直观的做法是对每个维度开个 \(n\times m\) 的 \(01\) 矩阵，\(a_{i,j}\) 为 \(1\) 表示，在这个维度下 \(a_{i}\le a_{j}\)，反之则是 \(a_{i}\gt a_{j}\)。如果我们要求每个维度都比 \(i\) 小的点的数量，直接把这 \(m\) 个维度的 \(01\) 矩阵的第 \(i\) 行与一下求 \(1\) 的个数就行了。
开 \(mn^2\) 的数组，bitset 也很难开的下，注意到单独的数组是没用的，所以在对每一维统计时直接与上之前的答案。对每一维排序，然后从小到大遍历物品，开一个临时 bitset 来存只考虑该维，值比当前位置小的位置，类似前缀的维护方法。注意初始化。排序时注意直接交换数组是 \(O(m)\) 的，所以只能对下标排序。一定要注意是 \(\le\) 还是 \(\lt\)。相当好写。
推个板子题
这题直接 bitset 预处理 \(m\) 维偏序，然后跑个相当显然的 \(O(n^2)\) dp 即可。注意为了保证只能从前面转移，dp 前按任意一维排个序，避免漏掉情况。比较卡常，写写快读快写。
教授の代码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ri register int
#define inf 0x3f3f3f3f
namespace inout
{
#define super faster
#ifdef super
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
template<typename tn> il void read(tn &x)
{
x=0;
register bool op=false;
register char ch=getchar();
while(ch<'0'||ch>'9')
{
op|=(ch=='-');
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
if(op)
{
x=~x+1;
}
}
template<typename tn> void writen(tn x)
{
if(x)
{
writen(x/10);
putchar(x%10|'0');
}
}
template<typename tn> il void write(tn x)
{
if(!x)
{
putchar('0');
return;
}
if(x<0)
{
putchar('-');
x=~x+1;
}
writen(x);
}
}using namespace inout;
int a,b,c[5005],qwer,ap[5005],ac;
bitset<5005>can[5005],now;
long long dp[5005],ans;
struct node
{
int val[505];
}pit[5005];
il bool cmp(int x,int y)
{
return pit[x].val[qwer]<pit[y].val[qwer];
}
int main()
{
read(a);
read(b);
for(ri i=1;i<=b;i++)
{
read(c[i]);
pit[i].val[0]=i;
can[i].set();
ap[i]=i;
}
for(ri i=1;i<=a;i++)
{
for(ri j=1;j<=b;j++)
{
read(pit[j].val[i]);
}
}
for(ri i=1;i<=a;i++)
{
qwer=i;
sort(ap+1,ap+1+b,cmp);
now.reset();
ri bg=0;
for(ri j=1;j<=b;j++)
{
if(pit[ap[j]].val[i]!=pit[ap[bg]].val[i])
{
while(bg!=j)
{
now.set(pit[ap[bg]].val[0]);
bg++;
}
bg=j;
}
can[pit[ap[j]].val[0]]&=now;
}
}
for(ri i=1;i<=b;i++)
{
ri h=pit[ap[i]].val[0];
for(ri j=1;j<i;j++)
{
ri k=pit[ap[j]].val[0];
if(can[h][k])
{
dp[h]=max(dp[h],dp[k]);
}
}
dp[h]+=c[h];
ans=max(ans,dp[h]);
}
write(ans);
return 0;
}
别 D 了，CDQ 分治会不了一点。