Location>code7788 >text

Flowers: bitset solves for high-dimensional partial orders

Popularity:3 ℃/2024-11-08 11:20:03

please refer to the previous section (of a book)

One-dimensional partials are done directly, two-dimensional partials are set in a line segment tree or subsumption sort, three-dimensional partials can be tree over tree or CDQ over tree, and what about four-dimensional partials? You can CDQ a tree over a tree. What about five-dimensional partial order? It can be found, whether CDQ partition or tree, it is difficult to continue to nest, and then write down not only a huge amount of code, but also difficult to adjust, the efficiency is also quite low. Tree or CDQ nesting\(m\) The dimensional partial order time complexity is\(O(n\log^{m-1}n)\)But we can use STL bitsets to create a new set of bitsets in STL. However, we use STL bitsets that can be used in the\(O(\tfrac{n^2m}{w})\) of excellent complexity within the solution of this problem.

Prior knowledge:

Basic usage of bitset

The most intuitive way to do this is to open a for each dimension\(n\times m\) (used form a nominal expression)\(01\) Matrix.\(a_{i,j}\) because of\(1\) Indicates that under this dimension\(a_{i}\le a_{j}\)and vice versa.\(a_{i}\gt a_{j}\). If we require each dimension to be higher than\(i\) The small number of dots that directly puts this\(m\) dimensional\(01\) Matrix of the first\(i\) behavior and one-to-one correspondence\(1\) The number of the number of the number is enough.

write out (a prescription, check, invoice etc)\(mn^2\) The bitset is also difficult to open under the array, noting that a separate array is useless, so it is directly related to the previous answer above when counting each dimension. Sort each dimension, and then traverse the items from small to large, open a temporary bitset to store only consider the dimension, the value is smaller than the current position of the position, similar to the prefix maintenance method. Note the initialization. When sorting, note that directly swapping arrays is\(O(m)\) s, so only subscripts can be sorted. Be sure to note that the\(\le\) nevertheless\(\lt\). Pretty well written.

Push a board question

This is a straightforward bitset preprocessor.\(m\) dimensional partial order, and then run a fairly obvious\(O(n^2)\) dp is sufficient. Note that in order to ensure that only from the front of the transfer, dp before any one-dimensional ordering, to avoid missing the case. Compare the card often, write write fast read fast write.

Professor's Substitute
#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);
		();
		ri bg=0;
		for(ri j=1;j<=b;j++)
		{
			if(pit[ap[j]].val[i]!=pit[ap[bg]].val[i])
			{
				while(bg!=j)
				{
					(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;
}

Don't D. The CDQ partition won't work.