# [题解] 2023 杭电多校 King's Ruins [偏序][bitset][dp]

# 题目大意 $\footnotesize^{传送门}$

六维偏序 $dp$ 。

# 高维偏序 bitset 做法

一维、二维、三维偏序分别有排序、排序 + 一维数据结构、 $CDQ$ 分治的做法，比较经典。维数再高点，多层嵌套的 $CDQ$ 、多层嵌套数据结构，复杂度都不会太理想。
专门处理高维查询的数据结构 $K-D Tree$ 呢？单次查询的复杂度 $\mathcal{O}(n^{\frac{k-1}{k}})$ ，这题来看， $n=5\times 10^4,k=5$ ，其实复杂度也是可以接受的。
高维偏序还有另外偏优美的暴力的解法，运用 $bitset$ ，详见 FHR 高维偏序
简而言之的思想就是，对于一个元素，分别求每一维的偏序关系，然后取交，就是高维偏序关系。
这里贴一个模板题和模板代码

	#include<cstdio>
	#include<bitset>
	#include<cmath>
	#include<algorithm>
	#include<cstring>

	int read(){
	int out(0),c(getchar());
	for(;c<'0' \|\| c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
	out=(out<<1)+(out<<3)+(c^48);
	return out;
	}

	const int MAXN=4e4+10;
	const int MAXB=233;
	const int MAXK=7;

	int nowk;
	struct P{
	int a[MAXK];
	bool operator < (const P &rv)const{
	return a[nowk]<rv[nowk];
	}
	int operator [] (const int &x)const{
	return a[x];
	}
	int &operator [] (const int &x){
	return a[x];
	}
	}p[MAXN];
	int idx[MAXK][MAXN];

	int N,K,B;
	std::bitset<MAXN> bs[MAXK][MAXB];
	std::bitset<MAXN> res,tmp;

	inline std::bitset<MAXN> get(int k,int v){
	int b=v/B-1;
	std::bitset<MAXN> res(0);
	if(b>=0)
	res=bs[k][b];
	for(int x=v/B*B;x<=v;++x)
	res.set(idx[k][x]);
	return res;
	}

	int main(){
	freopen("partial_order_plus.in","r",stdin);
	freopen("partial_order_plus.out","w",stdout);

	N=read(),K=read();
	for(int k=1;k<=K;++k)
	for(int i=0;i<N;++i)
	p[i][k]=read()-1;
	for(int i=0;i<N;++i)
	p[i][0]=i;
	memset(idx,0xff,sizeof(idx));
	B=sqrt(N);
	for(nowk=0;nowk<=K;++nowk){
	std::sort(p,p+N);
	for(int i=0;i<N;++i){
	// printf("%d ",p[i][nowk]);
	idx[nowk][p[i][nowk]]=p[i][0];
	bs[nowk][p[i][nowk]/B].set(p[i][0]);
	}
	// printf("\n");
	for(int b=1;b*B<N;++b)
	bs[nowk][b]\|=bs[nowk][b-1];
	}
	long long ans=0;
	for(int i=0;i<N;++i){
	res.set();
	for(int k=0;k<=K;++k)
	res&=get(k,p[i][k]-1);
	ans+=res.count();
	}
	printf("%lld\n",ans);
	}

# 题解

这题是一个在五维偏序（下标另外也算一维，但因为按顺序转移，所以忽略）关系上转移的 $dp$ 问题
对一个点，想办法求出比它 “小”（指的每一维都小于，下同）的点集，用这个点集中 $dp$ 最大值进行转移。然而我们存不下所有范围的点，所以分块。
分块大小为 $B$ ，对于每个分块，块内暴力转移，然后考虑这一块对后面点的贡献。
对于后面的每个点 $x$ ，求出当前块内的比 x 小的点集 $\footnotesize^{(1)}$ ，然后这个点集的最大值 $\footnotesize^{(2)}$ 转移到 $x$ 。
第 $(1)$ 步其实很好实现，扫一遍块内的点，将每一维的权值存入 $bitset$ ，然后滚一边前缀按位或，得到每一维、小于等于某权值的点集。转移时按点 x 的各维权值，将我们得到的前缀值按位与起来就是了。
第 $(2)$ 步，如何快速得到一个集合所有点的最大值？只能预处理。所以我们块的大小限制在 $\log{n}$ 。
这样这个问题看起来是解决了。复杂度是 $\mathcal{O}(\frac{n^2}{\log{n}})$ 的。
然而为了减少常数，还得优化一些东西。。
我们在第 $(1)$ 步求的点集，一个块点集大小是 $\log{n}$ 也就是 $16$ 。实际上我们可以对于四个块求点集，正好存入 $unsigned long long$ 中（实际上就是 $bitset$ 的用法），每个块取点集时，只取其中一段即可。这样的话这部分复杂度常数减小到 $\frac{1}{4}$ 。
大概 $10s$ 可过。（然而似乎是不如 $K-D Tree$ 优秀）有时间补一下 $K-D Tree$ 做法，也是纯板子。

# 代码

$std$ 写得实在看不懂。他貌似还给长度 $16$ 的小块划分了大块，每次计算一个大块内部的 dp 值，然后再给后面转移；决策子集合的大小仍然是 $16$ ，所以还要四个一组压到 $unsignedlonglong$ 。。
~~然而最后跑出来时间还比我慢 1s~~

	#include<cstdio>
	#include<cstring>
	#include<algorithm>
	#include<functional>
	int read(){
	int out(0),c(getchar());
	for(;c<'0' \|\| c>'9';c=getchar());
	for(;c<='9' && c>='0';c=getchar())
	out=(out<<3)+(out<<1)+(c^48);
	return out;
	}

	inline void Max(int &a,const int &b){
	if(b>a)a=b;
	}
	inline int min(const int &a,const int &b){
	return a<b ? a : b;
	}
	inline int max(const int &a,const int &b){
	return a>b ? a : b;
	}

	const int MAXN=5e4+10;

	typedef unsigned long long ull;

	int p[MAXN][5];

	int T,N,B;
	int a[MAXN];
	int apos[5][MAXN];
	int f[MAXN],bmax[1<<16];
	ull tset[5][MAXN];
	int ts[5][MAXN],tot;

	bool le(int a[],int b[]){
	return a[0]<=b[0]
	&& a[1]<=b[1]
	&& a[2]<=b[2]
	&& a[3]<=b[3]
	&& a[4]<=b[4];
	}

	void work(){
	N=read();
	for(int i=1;i<=N;++i){
	for(int j=0;j<5;++j)
	p[i][j]=read();
	a[i]=read();
	}
	for(int i=0;i<5;++i){
	for(int j=1;j<=N;++j)
	apos[i][j]=j;
	std::sort(apos[i]+1,apos[i]+1+N,[=](const int &lv,const int &rv){
	return p[lv][i]>p[rv][i];
	});
	}
	B=16;
	f[0]=0;
	for(int i=1;i<=N;++i)
	f[i]=a[i];
	for(int l=1;l<=N;l+=B){
	int r=min(N,l+B-1);
	int len=r-l+1;
	const int bi=(l-1)/B%4;
	const int ms=(1<<len)-1;
	for(int i=l+1;i<=r;++i)
	for(int j=l;j<i;++j)
	if(le(p[j],p[i]))
	Max(f[i],f[j]+a[i]);
	bmax[0]=0;
	for(int i=0;i<len;++i)
	bmax[1<<i]=f[l+i];
	for(int s=1;s<=ms;++s)
	bmax[s]=max(bmax[s&-s],bmax[s^(s&-s)]);
	if(bi==0){
	++tot;
	for(int k=0;k<5;++k){
	for(int i=0,rb=min(len*4-1,N-l);i<=rb;++i)
	tset[k][p[l+i][k]]=ts[k][p[l+i][k]]==tot
	? (tset[k][p[l+i][k]]\|1ull<<i)
	: (ts[k][p[l+i][k]]=tot, 1ull<<i);
	for(int i=1;i<=N;++i)
	tset[k][i]=ts[k][i]==tot
	? (tset[k][i]\|tset[k][i-1])
	: (ts[k][i]=tot, tset[k][i-1]);
	}
	}
	for(int i=r+1;i<=N;++i){
	ull s=tset[0][p[i][0]]
	&tset[1][p[i][1]]
	&tset[2][p[i][2]]
	&tset[3][p[i][3]]
	&tset[4][p[i][4]];
	Max(f[i],bmax[(s>>(bi<<4))&ms]+a[i]);
	}
	}
	for(int i=1;i<=N;++i)
	printf("%d\n",f[i]);
	}

	int main(){
	// freopen("1002.in","r",stdin);
	// freopen("1002t.res","w",stdout);
	T=read();
	while(T--)
	work();
	return 0;
	}

dp 偏序 bitset

# [题解] 2023 杭电多校 King's Ruins [偏序][bitset][dp]

# 题目大意传送门\footnotesize^{传送门}传送门

# 高维偏序 bitset 做法

# 题解

# 代码

[题解] CF1864E Exotic Queries [区间问题][二维偏序]

ICPC2023 HongKong Sum of Numbers

# 题目大意 $\footnotesize^{传送门}$