1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

int inp[100003][2];
int n;
int repr[100003];
int sizes[100003];
pair<int,int> num_pos[200003];

int F(int a){
    if(repr[a] == a) return a;
    repr[a] = F(repr[a]);
    return repr[a];
}

void U(int a, int b){
    a = F(a);
    b = F(b);
    if(a == b) return;
    if(sizes[a] > sizes[b]) swap(a, b);
    sizes[b] += sizes[a];
    repr[a] = b;
}

int res[100003];
vector<int> p;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int a, k;
    cin >> n >> k;
    for(int i=0; i<2; i++){
        for(int j=0; j<n; j++){
            cin >> a;
            inp[j][i] = a;
            num_pos[a] = {j,i};
        }
    }

    int scc_count;
    int x,y;

    for(int st=1; st<=2*n; st++){
        for(int i=1; i<=n*2; i++){
            repr[i] = i;
            sizes[i] = 1;
        }
        scc_count = 0;
        for(int en=st; en<=n*2; en++){
            p.clear();
            x = num_pos[en].first;
            y = num_pos[en].second;
            a = inp[x][(y+1)%2];
            if(a>=st && a<en) p.push_back(F(a));
            a = inp[(x+1)%n][y];
            if(a>=st && a<en) p.push_back(F(a));
            a = inp[(x+n-1)%n][y];
            if(a>=st && a<en) p.push_back(F(a));
            if(p.size()==0){
                scc_count++;
                res[scc_count]++;
                // cout << st << ' ' << en << ' ' << scc_count << '\n';
                continue;
            }
            
            a = inp[x][(y+1)%2];
            if(a>=st && a<en) U(a,en);
            a = inp[(x+1)%n][y];
            if(a>=st && a<en) U(a,en);
            a = inp[(x+n-1)%n][y];
            if(a>=st && a<en) U(a,en);

            sort(p.begin(), p.end());
            for(int i=1; i<p.size(); i++){
                if(p[i] != p[i-1]) scc_count--;
            }
            res[scc_count]++;
            // cout << st << ' ' << en << ' ' << scc_count << '\n';
        }
    }
    for(int i=1; i<=k; i++) cout << res[i] << ' ';
}