D. Fixed Prefix Permutations(字典树)

• Problem - D - Codeforces

题意：

• 给一个n行m列的关于m的排列数组，n个m的排列，设为q[n]
• 对于q[i]，找到最长的q[q[i]]排列是1，2，...，k，美丽值是k
• 输出每一个的k

思路：

• 看样例一可以大概知道字典树是该怎么做
• 对于1~m，找到原先的关于m的排列，数字的位置的坐标，树中插入
• 然后查询原数组能走的最长路径

#include<bits/stdc++.h>
#define debug1(a) cout<<#a<<'='<< a << endl;
#define debug2(a,b) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<endl;
#define debug3(a,b,c) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<endl;
#define debug4(a,b,c,d) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<"  "<<#d<<" = "<<d<<endl;
#define debug5(a,b,c,d,e) cout<<#a<<" = "<<a<<"  "<<#b<<" = "<<b<<"  "<<#c<<" = "<<c<<"  "<<#d<<" = "<<d<<"  "<<#e<<" = "<<e<<endl;
#define endl "\n"
#define fi first
#define se second

#define int long long
//#define int __int128
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;

//#pragma GCC optimize(3,"Ofast","inline")
//#pragma GCC optimize(2)

//常数定义
const double eps = 1e-4;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 5e4+10;
int a[N][15];

int son[15*N][15], idx;
int n,m;
int start;

void insert(int a[])          
{
    int p = start;
    for (int i = 1; i <= m; i ++ )
    {
        int u = a[i];
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
}

int query(int a[])
{
    int p = start;
    int step = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int u = a[i];
        if (!son[p][u]) return step;
        p = son[p][u];
        step ++;
    }
    return step;
}


void solve() 
{
    start = idx;

    cin >> n >> m;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            cin >> a[i][j];
        }
        int temp[15];
        for(int j = 1;j <= m;j ++)
        {
            temp[a[i][j]] = j;
        }
        insert(temp);
    }

    for(int i = 1;i <= n;i ++)
    {
        cout << query(a[i]) << " ";
    }
    cout << endl;

}

signed main()
{
    
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int T = 1;cin >> T;

    while(T--){
        //puts(solve()?"YES":"NO");
        solve();
    }
    return 0;

}
/*

*/