2639. [HZOI 2015] 偏序++

【题目描述】

给定一个有$n$个元素的序列，元素编号为$1$~$n$，每个元素有k个属性$p^1$,$p^2$,$p^3$,...,$p^k$，求序列中满足$i<j$且$1<=t<=k,p^t_i<p^t_j$的数对$(i,j)$的个数。

【输入格式】

第一行两个整数$n$，$k$，表示序列长度和属性个数。

接下来$k$行，每行$n$个整数，第$t$行表示$n$个元素的第$p^t$个属性。

【输出格式】

共1行，表示满足要求的数对个数。

【样例输入】

5 4
1 4 5 2 3
3 5 2 1 4
2 3 4 1 5
2 3 1 5 4

【样例输出】

2

【样例解释】

每个元素4个属性，满足要求的数对为(1,2)，(1,5)。

【数据范围与约定】

对于30%的数据，$n$<=5000,k<=6。

另有40%的数据，1<=$n$<=40000，k=2。

对于100%的数据，1<=$n$<=40000，k<=6。保证对于所有元素的$p^t$属性组成一个$1$~$n$的排列。

请注意常数因子带来的程序效率上的影响。

【来源】

HZOI2015