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
86
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <queue>

using namespace std;

const int MAXN = 100000;
const int MAXK = 10;

int plot[MAXN+5][2];
int wynik[MAXK+5];

bool odw[MAXN+5][2];

int rows[MAXN*2+10];
int cols[MAXN*2+10];

void inline dodaj(int row, int col, queue<int> &q, int l, int r) {
	if (!odw[col][row] && plot[col][row] >= l && plot[col][row] <= r) {
		q.push(row+col*2);
	}
}

int policz_ciekawosc(int l, int r, int n, int k) {
	memset(odw, 0, n*sizeof(bool)*2);
	queue<int> q;
	int wynik = 0, row, col;
	for (int w = l; w <=r; ++w) {
		int i = cols[w];
		int j = rows[w];
			if (!odw[i][j] && plot[i][j] >= l && plot[i][j] <= r) {
				++wynik;
				if (wynik > k) {
					return wynik;
				}
				q.push(2*i + j);
				while(!q.empty()) {
					row = q.front() % 2;
					col = q.front() / 2;
					q.pop();
					odw[col][row] = true;
					if (row == 0) {
						dodaj(1, col, q, l, r);
					} else {
						dodaj(0, col, q, l, r);
					}
					dodaj(row, (col+1)%n, q, l, r);
					dodaj(row, (col+n-1)%n, q, l, r);
				}
			}
	}
	return wynik;
}

#define NDEBUG

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	for (int j = 0; j < 2; ++j) {
		for (int i = 0; i < n; ++i) {
			scanf("%d", &plot[i][j]);
			--plot[i][j];
			rows[plot[i][j]] = j;
			cols[plot[i][j]] = i;
		}
	}
	int maxcolor = 2*n;
	for (int i = 1; i <=k; ++i) {
		wynik[i] = 0;
	}
	wynik[1] = maxcolor;
	for(int l = 0; l < maxcolor; ++l) {
		for(int r = l+1; r < maxcolor; ++r) {
			int ciek = policz_ciekawosc(l, r, n, k);
			if (ciek <= k) {
				++wynik[ciek];
			}
		}
	}
	for	(int i = 1; i<=k;++i) {
		printf("%d ", wynik[i]);
	}
}