首页 题解

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

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

六维偏序dpdp。

# 高维偏序 bitset 做法

一维、二维、三维偏序分别有排序、排序 + 一维数据结构、CDQCDQ 分治的做法，比较经典。维数再高点，多层嵌套的CDQCDQ、多层嵌套数据结构，复杂度都不会太理想。
专门处理高维查询的数据结构K−DTreeK-D Tree 呢？单次查询的复杂度O(nk−1k)\mathcal{O}(n^{\frac{k-1}{k}})，这题来看，n=5×104,k=5n=5\times 10^4,k=5，其实复杂度也是可以接受的。
高维偏序还有另外偏优美的暴力的解法，运用bitsetbitset，详见 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);
}
# 题解
这题是一个在五维偏序（下标另外也算一维，但因为按顺序转移，所以忽略）关系上转移的dpdp 问题
对一个点，想办法求出比它 “小”（指的每一维都小于，下同）的点集，用这个点集中dpdp 最大值进行转移。然而我们存不下所有范围的点，所以分块。
分块大小为BB，对于每个分块，块内暴力转移，然后考虑这一块对后面点的贡献。
对于后面的每个点xx，求出当前块内的比 x 小的点集(1)\footnotesize^{(1)}，然后这个点集的最大值(2)\footnotesize^{(2)} 转移到xx。
第(1)(1) 步其实很好实现，扫一遍块内的点，将每一维的权值存入bitsetbitset，然后滚一边前缀按位或，得到每一维、小于等于某权值的点集。转移时按点 x 的各维权值，将我们得到的前缀值按位与起来就是了。
第(2)(2) 步，如何快速得到一个集合所有点的最大值？只能预处理。所以我们块的大小限制在log⁡n\log{n}。
这样这个问题看起来是解决了。复杂度是O(n2log⁡n)\mathcal{O}(\frac{n^2}{\log{n}}) 的。
然而为了减少常数，还得优化一些东西。。
我们在第(1)(1) 步求的点集，一个块点集大小是log⁡n\log{n} 也就是1616。实际上我们可以对于四个块求点集，正好存入unsignedlonglongunsigned long long 中（实际上就是bitsetbitset 的用法），每个块取点集时，只取其中一段即可。这样的话这部分复杂度常数减小到14\frac{1}{4}。
大概10s10s 可过。（然而似乎是不如K−DTreeK-D Tree 优秀）有时间补一下K−DTreeK-D Tree 做法，也是纯板子。
# 代码
stdstd 写得实在看不懂。他貌似还给长度1616 的小块划分了大块，每次计算一个大块内部的 dp 值，然后再给后面转移；决策子集合的大小仍然是1616，所以还要四个一组压到unsignedlonglongunsignedlonglong。。
然而最后跑出来时间还比我慢 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;
}
  
 更新于   阅读次数  次