[COGS2639]偏序++

题目大意：

\(n(n\le40000)\)个\(k(k\le7)\)元组，求\(k\)维偏序。

思路：

分块后用bitset维护。

时间复杂度\(\mathcal O(kn\sqrt n)\)。

源代码：

#include<cmath>

#include<cstdio>

#include<cctype>

#include<bitset>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int K=7,N=40000,B=200;

std::bitset<N> set[7][B],tmp;

int n,k,bel[N],end[B],block,a[K][N],pos[K][N];

int main() {

	freopen("partial_order_plus.in","r",stdin);

	freopen("partial_order_plus.out","w",stdout);

	n=getint(),k=getint();

	block=sqrt(n);

	for(register int i=0;i<n;i++) {

		end[bel[i]=i/block]=i;

	}

	for(register int i=0;i<n;i++) a[0][i]=i;

	for(register int i=1;i<=k;i++) {

		for(register int j=0;j<n;j++) {

			a[i][j]=getint()-1;

			pos[i][a[i][j]]=j;

		}

	}

	for(register int i=0;i<=k;i++) {

		for(register int j=0;j<n;j++) {

			set[i][bel[a[i][j]]][j]=true;

		}

		for(register int j=1;j<=(n-1)/block;j++) {

			set[i][j]|=set[i][j-1];

		}

	}

	int64 ans=0;

	for(register int i=0;i<n;i++) {

		tmp=set[0][bel[i]];

		for(register int j=i;j<=end[bel[i]];j++) {

			tmp[j]=false;

		}

		for(register int j=1;j<=k;j++) {

			tmp&=set[j][bel[a[j][i]]];

			for(register int k=a[j][i];k<=end[bel[a[j][i]]];k++) {

				tmp[pos[j][k]]=false;

			}

		}

		ans+=tmp.count();

	}

	printf("%lld\n",ans);

	return 0;

}