记录编号	516871	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] 偏序++	最终得分	100
用户昵称	ytxytx	是否通过	通过
代码语言	C++	运行时间	7.299 s
提交时间	2018-10-26 16:57:02	内存使用	9.47 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>

int n,m;
const int inf=1<<30;

namespace Kd_tree{
	int nowD;

	struct node{
		int mini[7],maxi[7];
		int size,L,R;
	}T[100000];
	int tot,root;

	struct _node{
		int W[7];
	}U[100000];
	inline bool cmp(_node A,_node B){return A.W[nowD]<B.W[nowD];}

	inline double Pow(double k){return k*k;}

	int calc(int L,int R){
		double aver[7];
		double sq[7];
		for (int i=0;i<7;i++) aver[i]=sq[i]=0;
		for (int i=L;i<=R;i++)
			for (int j=0;j<m;j++) aver[j]+=U[i].W[j];
		for (int i=0;i<m;i++) aver[i]/=(R-L+1);
		for (int i=L;i<=R;i++)
			for (int j=0;j<m;j++) sq[j]+=Pow(U[i].W[j]-aver[j]);
		int maxi=0;
		for (int i=1;i<m;i++) if (sq[i]>sq[maxi]) maxi=i;
		return maxi;
	}

	void update(int now){
		if (!T[now].L&&!T[now].R) return;
		for (int i=0;i<m;i++){
			T[now].maxi[i]=-inf;
			T[now].mini[i]=inf;
		}
		T[now].size=0;
		if (T[now].L){
			for (int i=0;i<m;i++){
				T[now].mini[i]=std::min(T[now].mini[i],T[T[now].L].mini[i]);
				T[now].maxi[i]=std::max(T[now].maxi[i],T[T[now].L].maxi[i]);
			}
			T[now].size+=T[T[now].L].size;
		}
		if (T[now].R){
			for (int i=0;i<m;i++){
				T[now].mini[i]=std::min(T[now].mini[i],T[T[now].R].mini[i]);
				T[now].maxi[i]=std::max(T[now].maxi[i],T[T[now].R].maxi[i]);
			}
			T[now].size+=T[T[now].R].size;
		}
	}

	void build(int &now,int L,int R){
		now=++tot;
		if (L==R){
			for (int i=0;i<m;i++) T[now].mini[i]=T[now].maxi[i]=U[L].W[i];
			T[now].size=1;
			return;
		}
		nowD=calc(L,R);
		int mdl=(L+R)>>1;
		std::nth_element(U+L,U+mdl,U+R+1,cmp);
		build(T[now].L,L,mdl);
		build(T[now].R,mdl+1,R);
		update(now);
	}

	int query(int now,_node P){
		for (int i=0;i<m;i++) if (T[now].mini[i]>P.W[i]) return 0;
		bool rt=true;
		for (int i=0;i<m;i++) if (T[now].maxi[i]>P.W[i]){rt=false;break;}
		if (rt) return T[now].size;
		return query(T[now].L,P)+query(T[now].R,P);
	}
}

int ans;

int main(){
	freopen("partial_order_plus.in","r",stdin);
	freopen("partial_order_plus.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int j=0;j<m;j++)
		for (int i=1;i<=n;i++)
			scanf("%d",&Kd_tree::U[i].W[j]),Kd_tree::U[i].W[m]=i;
	m++;
	Kd_tree::build(Kd_tree::root,1,n);
	for (int i=1;i<=n;i++)
		for (int j=0;j<m;j++)
			Kd_tree::U[i].W[j]--;
	for (int i=1;i<=n;i++) ans+=Kd_tree::query(Kd_tree::root,Kd_tree::U[i]);
	printf("%d\n",ans);
}