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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int N = 1e5 + 10, K = 11, inf = 1e9;
int n, k, a[2][N], use[2][N];
pair<int, int> rev[2 * N];
struct info {
	int mn;
	i64 way[K];
	info() {
		mn = inf;
		memset(way, 0, sizeof way); 
	}
	friend info operator + (const info &x, const info &y) {
		if(x.mn < y.mn) {
			info z = x;
			int d = y.mn - x.mn;
			for(int i = 0; i <= k - d; i ++) z.way[i + d] += y.way[i];
			return z;
		} else {
			info z = y;
			int d = x.mn - y.mn;
			for(int i = 0; i <= k - d; i ++) z.way[i + d] += x.way[i];
			return z;
		}
	}
};
namespace SGT {
	#define ls u << 1
	#define rs u << 1 | 1
	int tag[N << 3];
	info sum[N << 3];
	void seta(int u, int k) {
		tag[u] += k, sum[u].mn += k;
	}
	void dw(int u) {
		if(tag[u]) seta(ls, tag[u]), seta(rs, tag[u]), tag[u] = 0;
	}
	void upd(int u, int l, int r, int ql, int qr, int k) {
		if(l >= ql && r <= qr) return seta(u, k);
		int mid = l + r >> 1; dw(u);
		if(ql <= mid) upd(ls, l, mid, ql, qr, k);
		if(qr > mid) upd(rs, mid + 1, r, ql, qr, k);
		sum[u] = sum[ls] + sum[rs];
	}
	info query(int u, int l, int r, int ql, int qr) {
		if(l >= ql && r <= qr) return sum[u];
		int mid = l + r >> 1; dw(u);
		if(qr <= mid) return query(ls, l, mid, ql, qr);
		else if(ql > mid) return query(rs, mid + 1, r, ql, qr);
		else return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
	}
	void build(int u, int l, int r) {
		sum[u].way[0] = r - l + 1, sum[u].mn = 0;
		if(l < r) {
			int mid = l + r >> 1;
			build(ls, l, mid), build(rs, mid + 1, r);
		}
	}
	#undef ls
	#undef rs
}
int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for(int c : {0, 1}) for(int i = 1; i <= n; i ++) cin >> a[c][i], rev[a[c][i]] = {c, i};
	a[0][n + 1] = a[0][1]; a[1][n + 1] = a[1][1];
	a[0][0] = a[0][n], a[1][0] = a[1][n];
	static int ts[N];
	auto upd = [&] (int p, int k) {
		if(use[0][p] || use[1][p]) {
			int l1 = -1, r1 = - 1, l2 = -1, r2 = -1;
			if(use[0][p] > use[0][p - 1]) l1 = use[0][p - 1] + 1, r1 = use[0][p];
			if(use[1][p] > use[1][p - 1]) l2 = use[1][p - 1] + 1, r2 = use[1][p];
			if(use[0][p] && use[0][p - 1] && l2 != -1) l2 = max(l2, min(use[0][p - 1], use[0][p]) + 1);
			if(use[1][p] && use[1][p - 1] && l1 != -1) l1 = max(l1, min(use[1][p - 1], use[1][p]) + 1);
			if(l1 > r1) l1 = r1 = -1;
			if(l2 > r2) l2 = r2 = -1;
			if(l1 != -1 && l2 != -1 && max(l1, l2) <= min(r1, r2)) {
				l1 = min(l1, l2), r1 = max(r1, r2);
				l2 = -1, r2 = -1;
			}
			if(l1 != -1) SGT::upd(1, 1, 2 * n, l1, r1, k);
			if(l2 != -1) SGT::upd(1, 1, 2 * n, l2, r2, k);

		}
	};
	info ans;
	SGT::build(1, 1, 2 * n);
	for(int i = 1; i <= 2 * n; i ++) {
		auto [x, y] = rev[i];
		upd(y, -1);
		upd(y + 1, -1);
		use[x][y] = i;
		if(y == 1) use[x][n + 1] = i;
		if(y == n) use[x][0] = i;
		upd(y, 1);
		upd(y + 1, 1);
		ans = ans + SGT::query(1, 1, 2 * n, 1, i);
	}
	if(ans.mn == 0) {
		ans.way[1] += ans.way[0];
	} else {
		for(int i = k; i >= 1; i --) ans.way[i] = ans.way[i - 1];
	}
	for(int i = 1; i <= k; i ++) cout << ans.way[i] << ' ';
	return 0;
}