首页 > 其他分享 >鲜花:bitset求解高维偏序

鲜花:bitset求解高维偏序

时间:2024-11-08 11:21:50浏览次数:1  
标签:偏序 ch putchar CDQ define 高维 bitset

书接上回

一维偏序直接做、二维偏序套线段树或归并排序、三维偏序可以树套树或者 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 分治会不了一点。

标签:偏序,ch,putchar,CDQ,define,高维,bitset
From: https://www.cnblogs.com/ywhhdjser-97/p/18534367

相关文章

  • 子集枚举优化与高维前缀和
    前缀和与二维前缀和考虑一个序列\(a\),我们如何快速求出区间\([l,r]\)的元素和呢?这很简单,我们只需求出它的前缀和序列\(\mathrm{sum}(i)=\sum_{k=1}^ia_i\),那么答案即为\(\mathrm{sum}(r)-\mathrm{sum}(l-1)\)。而对于序列\(\mathrm{sum}\),有\(\mathrm{sum}(i)=......
  • 高维前缀和
    高维前缀和二维前缀和一般的做法是容斥:for(inti=1;i<=n;++i)for(intj=1;j<=n;++j)sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];实际上也可以固定其他维度,依次在每一维上求前缀和,即:for(inti=1;i<=n;+......
  • Bitset容器与优化
    Bitset是啥某种神奇的容器,用于存储二进制。头文件:#include<bitset>定义方法:bitset<5>Bit1("10011");bitset<5>Bit2(4);“<>”中的内容代表容器的长度,相当于一个数组,但是每一位只能存储0......
  • 高维前缀和
    1原来我不会。子集枚举枚举一个集合的每个子集的所有子集。for(ints=0;s<(1<<n);s++){for(ints0=s;;s0=s0&(s0-1)){cout<<s0<<'';}}其中\(s0\)即为枚举的每个子集的所有子集。这是为什么?第一层循环中,我们枚举了一个子集。那么第二层循环中,我们就......
  • Python数据分析NumPy和pandas(五、NumPy高维数组的数学计算 2)
    一、Numpy的花式索引FancyIndexing花式索引FancyIndexing是NumPy采用的一个术语,用于描述使用整数数组进行索引。1.举例:用元组来创建一个8x4的二维数组zeros,并循环赋值:importnumpyasnparr=np.zeros((8,4))#为二维数组arr每行赋值foriinrange(8):arr[i......
  • ARC136C Circular Addition [高维前缀和]
    Description给定一个长度为\(n\)的正整数序列\(A\),求有多少对\((i,j)\)使得\(A_i+A_j\)不发生进位操作。\(A_i<10^6\)。Solution显然对于每个\(A_i\),设\(B_i=999999-A_i\),那么\(A_i\)可以和所有位上的数都小于等于\(B_i\)对应位上的数的数匹配,考虑用桶加前缀......
  • 《 C++ 修炼全景指南:十四 》大数据杀手锏:揭秘 C++ 中 BitSet 与 BloomFilter 的神奇性
    本篇博客深入探讨了C++中的两种重要数据结构——BitSet和BloomFilter。我们首先介绍了它们的基本概念和使用场景,然后详细分析了它们的实现方法,包括高效接口设计和性能优化策略。接着,我们通过对比这两种数据结构的性能,探讨了在不同应用场景中的选择依据。最后,博客还涵盖......
  • Note - 单 log 求排列全局三维偏序数量
    考虑容斥计数。令\(f_c\)为恰好\(c\)维偏序的数量。那么考虑\(i\)若对于\(j\)是\(x\)维偏序,那么\(j\)对于\(i\)就是\(3-x\)维偏序。于是可以知道有\(f_0=f_3,f_1=f_2\),进一步可以推出\(f_2+f_3=\frac{n(n-1)}{2}\)。那么接下来就要向\(f_2,f......
  • bitset
    1.位运算的常见函数__builtin_popcount(x)//x二进制内1的个数(unsignedint)__builtin_popcountll(x)//longlong版本__builtin_parity(x)//二进制下的1的个数的奇偶性__builtin_parityll(x)//longlong版本__builtin_ctz(x)//x二进制末尾0的个数__builtin_clz(x)//x二进......
  • 妙用编辑器:使用Notepad--宏功能提高维护指令生成生成效率
    应用场景日常维护工作中,需要快速生成一批指令来完成某些操作,比如:快速添加一批节点。目标指令列表如下:ADDNODE:ID=1,NAME="NODE_1";ADDNODE:ID=2,NAME="NODE_2";ADDNODE:ID=3,NAME="NODE_3";ADDNODE:ID=4,NAME="NODE_4";ADDNODE:ID=5,NAME="NODE_5&quo......