【模板】k维偏序
题目描述
给你 $k$ 个长为 $n$ 的数列 $A[1..k][1..n]$,$f(i)=\sum\limits_{j=1}^n[\forall 1\le d\le k,\,A[d][j]<A[d][i]]$,求出所有 $f(1..n)$。
输入输出格式
输入格式
第一行两个正整数 $n,\,k$。
后面 $n$ 行每行 $k$ 个正整数,表示 $A[1..k][i]$。
输出格式
$n$ 行,每行一个正整数分别表示 $f(1..n)$。
输入输出样例
输入样例 #1
10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1
输出样例 #1
3
3
0
0
0
0
0
0
0
0
输入样例 #2
4 2
5 3
2 7
1 4
3 9
输出样例 #2
0
1
0
2
说明
~~这题的数据范围应该是n=1e10,时限开1e11s,卡掉n^2k做法~~
$1\le n\le 1000$,$2\le k\le 8$,$1\le A[i][j]\le 10^9$。
这题暴力跑的会比某些复杂度优秀的做法快,然而用暴力水过去挺没意思的..