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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct FUNODE {
	int rank;
	int parent;
	int val;
};

struct FU {
	FUNODE* nodes;
	int platforms;

	void create(int n) {
		platforms = 0;
		nodes = new FUNODE[n*2];
		for (int i = 0; i < n*2; i++) {
			nodes[i].rank = 0;
			nodes[i].parent = i;
			nodes[i].val = i;
		}
	}

	int find(int a) {
		while (nodes[a].parent != a) {
			a = nodes[a].parent;
		}

		return a;
	}

	void unio(int a, int b) {
		if (a == b) return;

		FUNODE x = this->nodes[find(a)];
		FUNODE y = this->nodes[find(b)];

		if (x.rank > y.rank) {
			y.parent = x.val;
			platforms--;
			nodes[x.val] = x;
			nodes[y.val] = y;
		}
		else if (y.rank > x.rank) {
			x.parent = y.val;
			platforms--;
			nodes[x.val] = x;
			nodes[y.val] = y;
		}
		else if (x.val != y.val) {
			y.parent = x.val;
			x.rank++;
			platforms--;
			nodes[x.val] = x;
			nodes[y.val] = y;
		}
	}

	void addNode(int x, int y, int f, int t, int**& points, int n) {
		platforms++;
		int nx = (x + 1) % n;
		if (points[nx][y] >= f && points[nx][y] <= t) {
			unio(points[nx][y], points[x][y]);
		}
		nx = (x - 1 + n) % n;
		if (points[nx][y] >= f && points[nx][y] <= t) {
			unio(points[nx][y], points[x][y]);
		}
		int ny = (y + 1) % 2;
		if (points[x][ny] >= f && points[x][ny] <= t) {
			unio(points[x][ny], points[x][y]);
		}
	}
} fu;

int main() {
	int n, k;
	cin >> n >> k;

	int** nodes = new int*[n];
	int a;
	map<int, pair<int, int>> valToPos;

	for (int j = 0; j < n; j++) {
		nodes[j] = new int[2];

	}

	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a;
			a--;
			nodes[j][i] = a;
			valToPos[a] = { j,i };
		}
	}

	int* out = new int[k] {0};

	pair<int, int> tmp;
	//fu.create(n);
	for (int i = 0; i < n*2; i++) {
		fu.create(n);
		for (int j = i; j < n*2; j++) {
			tmp = valToPos[j];
			fu.addNode(tmp.first, tmp.second, i, j, nodes, n);
			if (fu.platforms <= k) out[fu.platforms - 1]++;
		}
	}

	for (int i = 0; i < k; i++) cout << out[i] << " ";
	return 0;
}