标签：10 le cdot Permutations int Prefix 排列 permutation Fixed

D. Fixed Prefix Permutations

You are given $n$ permutations $a_1, a_2, \dots, a_n$, each of length $m$. Recall that a permutation of length $m$ is a sequence of $m$ distinct integers from $1$ to $m$.

Let the beauty of a permutation $p_1, p_2, \dots, p_m$ be the largest $k$ such that $p_1 = 1, p_2 = 2, \dots, p_k = k$. If $p_1 \neq 1$, then the beauty is $0$.

The product of two permutations $p \cdot q$ is a permutation $r$ such that $r_j = q_{p_j}$.

For each $i$ from $1$ to $n$, print the largest beauty of a permutation $a_i \cdot a_j$ over all $j$ from $1$ to $n$ (possibly, $i = j$).

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($1 \le n \le 5 \cdot 10^4$; $1 \le m \le 10$) — the number of permutations and the length of each permutation.

The $i$-th of the next $n$ lines contains a permutation $a_i$ — $m$ distinct integers from $1$ to $m$.

The sum of $n$ doesn't exceed $5 \cdot 10^4$ over all testcases.

Output

For each testcase, print $n$ integers. The $i$-th value should be equal to the largest beauty of a permutation $a_i \cdot a_j$ over all $j$ ($1 \le j \le n$).

Example

input

3
3 4
2 4 1 3
1 2 4 3
2 1 3 4
2 2
1 2
2 1
8 10
3 4 9 6 10 2 7 8 1 5
3 9 1 8 5 7 4 10 2 6
3 10 1 7 5 9 6 4 2 8
1 2 3 4 8 6 10 7 9 5
1 2 3 4 10 6 8 5 7 9
9 6 1 2 10 4 7 8 3 5
7 9 3 2 5 6 4 8 1 10
9 4 3 7 5 6 1 10 8 2

output

1 4 4 
2 2 
10 8 1 6 8 10 1 7 

 

解题思路

　　暴力做法是直接枚举全部排列，本质上给定一个排列$p$，从所有的排列中找到一个$q_i$使得$p \cdot q_i$的美丽值最大，假设最大值为$k$，那么$p \cdot q_i$得到的排列就是$\{ 1,2, \ldots k, q_{p_{k+1}} \ ,  \ldots, q_{p_{m}} \}$。注意到就是求从$1$开始的上升前缀最长是多少。因此可以考虑用trie来存$n$个排列的信息，然后再枚举每一个排列来得到答案。

　　对于一个排列$p$，如果答案至少是$1$，那么首先就要找到第$p[1]$个位置是数值$1$的所有排列，以此类推如果答案至少是$2$，那么就要从第$p[1]$个位置是数值$1$的所有排列中再找到第$p[2]$个位置为$2$的排列。因此我们可以在trie中存每个排列中每个数值在排列中的下标位置，查询的时候就依次遍历$p[i]$，这样就可以找到一个匹配的最大前缀。

　　AC代码如下，时间复杂度为$O(n \times m)$：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int n, m;
 5 vector<vector<int>> a, tr;
 6 int idx;
 7 int pos[20];
 8 
 9 void insert() {
10     int p = 0;
11     for (int i = 1; i <= m; i++) {
12         if (!tr[p][pos[i]]) tr[p][pos[i]] = ++idx;
13         p = tr[p][pos[i]];
14     }
15 }
16 
17 int query(int u) {
18     int p = 0, ret = 0;
19     for (int i = 1; i <= m; i++) {
20         if (!tr[p][a[u][i]]) break;
21         ret++;
22         p = tr[p][a[u][i]];
23     }
24     return ret;
25 }
26 
27 void solve() {
28     scanf("%d %d", &n, &m);
29     idx = 0;
30     tr = vector<vector<int>>(n * m + 1, vector<int>(m + 1));
31     a = vector<vector<int>>(n + 1, vector<int>(m + 1));
32     for (int i = 1; i <= n; i++) {
33         for (int j = 1; j <= m; j++) {
34             scanf("%d", &a[i][j]);
35             pos[a[i][j]] = j;
36         }
37         insert();
38     }
39     for (int i = 1; i <= n; i++) {
40         printf("%d ", query(i));
41     }
42     printf("\n");
43 }
44 
45 int main() {
46     int t;
47     scanf("%d", &t);
48     while (t--) {
49         solve();
50     }
51 }

 

参考资料

　　Educational Codeforces Round 142 D(思维+字典树)：https://zhuanlan.zhihu.com/p/600835977

标签：10,le,cdot,Permutations,int,Prefix,排列,permutation,Fixed
From： https://www.cnblogs.com/onlyblues/p/17068988.html