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
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
#define maxn 100005
#define maxc 200010
#define maxk 11
#define N 262144
#define ll long long
#define pii pair <int, int>
#define fi first
#define se second
using namespace std;

int n, n2, k;
int wej[maxc];
ll wyn[maxk];

struct akt
{
	pii prz;
	int c;
};
vector <akt> akts[maxc];

void dodaj_akt(int tak1, int tak2, int nie1, int nie2)
{
	if(tak1 > tak2) swap(tak1, tak2);
	if(nie1 > nie2) swap(nie1, nie2);
	if((tak1<=nie1&&nie1<=tak2) || (tak1<=nie2&&nie2<=tak2)) return;
	pii poc = {1, tak1}, kon = {tak2, n2};
	if(nie1 < tak1) poc.fi = max(poc.fi, nie1+1);
	else kon.se = min(kon.se, nie1-1);
	if(nie2 < tak1) poc.fi = max(poc.fi, nie2+1);
	else kon.se = min(kon.se, nie2-1);
	akts[poc.fi].push_back({kon, 1});
	akts[poc.se+1].push_back({kon, -1});
}

struct info
{
	pii t[maxk];// [ktore minimum] {wart, ile}
	int przep;
	info()
	{
		fill(t, t+maxk, make_pair(maxc, 0));
		przep = 0;
	}
} drz[N<<1];
void dodaj_prz(int p, int k, int c, int tp = 1, int tk = N, int w = 1)
{
	if(p <= tp && tk <= k)
	{
		drz[w].t[0].fi+=c, drz[w].t[1].fi+=c, drz[w].t[2].fi+=c, drz[w].t[3].fi+=c, drz[w].t[4].fi+=c, drz[w].t[5].fi+=c, drz[w].t[6].fi+=c, drz[w].t[7].fi+=c, drz[w].t[8].fi+=c, drz[w].t[9].fi+=c, drz[w].t[10].fi+=c;
		drz[w].przep += c;
		return;
	}
	if(drz[w].przep)
	{
		drz[w<<1].t[0].fi+=drz[w].przep, drz[w<<1].t[1].fi+=drz[w].przep, drz[w<<1].t[2].fi+=drz[w].przep, drz[w<<1].t[3].fi+=drz[w].przep, drz[w<<1].t[4].fi+=drz[w].przep, drz[w<<1].t[5].fi+=drz[w].przep, drz[w<<1].t[6].fi+=drz[w].przep, drz[w<<1].t[7].fi+=drz[w].przep, drz[w<<1].t[8].fi+=drz[w].przep, drz[w<<1].t[9].fi+=drz[w].przep, drz[w<<1].t[10].fi+=drz[w].przep;
		drz[w<<1].przep += drz[w].przep;
		drz[(w<<1)+1].t[0].fi+=drz[w].przep, drz[(w<<1)+1].t[1].fi+=drz[w].przep, drz[(w<<1)+1].t[2].fi+=drz[w].przep, drz[(w<<1)+1].t[3].fi+=drz[w].przep, drz[(w<<1)+1].t[4].fi+=drz[w].przep, drz[(w<<1)+1].t[5].fi+=drz[w].przep, drz[(w<<1)+1].t[6].fi+=drz[w].przep, drz[(w<<1)+1].t[7].fi+=drz[w].przep, drz[(w<<1)+1].t[8].fi+=drz[w].przep, drz[(w<<1)+1].t[9].fi+=drz[w].przep, drz[(w<<1)+1].t[10].fi+=drz[w].przep;
		drz[(w<<1)+1].przep += drz[w].przep;
		drz[w].przep = 0;
	}
	int sr = (tp+tk)>>1;
	if(p <= sr) dodaj_prz(p, k, c, tp, sr, w<<1);
	if(sr < k) dodaj_prz(p, k, c, sr+1, tk, (w<<1)+1);
	int ita = 0, itb = 0;
	for(int i = 0; i < maxk; ++i)
	{
		drz[w].t[i].fi = min(drz[w<<1].t[ita].fi, drz[(w<<1)+1].t[itb].fi);
		drz[w].t[i].se = 0;
		if(drz[w<<1].t[ita].fi == drz[w].t[i].fi) drz[w].t[i].se += drz[w<<1].t[ita++].se;
		if(drz[(w<<1)+1].t[itb].fi == drz[w].t[i].fi) drz[w].t[i].se += drz[(w<<1)+1].t[itb++].se;
		if(drz[w].t[i].fi > drz[w].t[0].fi+10) break;
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	n2 = n*2;
	for(int i = 1; i <= n2; ++i) cin >> wej[i];
	
	for(int i = 1; i <= n; ++i)
	{
		int i1 = i%n+1;
		dodaj_akt(wej[i], wej[i], wej[i1], wej[n+i]);
		dodaj_akt(wej[n+i], wej[n+i], wej[n+i1], wej[i]);
		dodaj_akt(wej[i], wej[n+i], wej[i1], wej[n+i1]);
	}
	
	for(int i = 1; i <= n2; ++i) drz[N-1+i].t[0] = {0, 1};
	for(int i = N-1; i; --i) drz[i].t[0] = {0, drz[i<<1].t[0].se+drz[(i<<1)+1].t[0].se};
	
	for(int i = 1; i <= n2; ++i)
	{
		for(akt j : akts[i]) dodaj_prz(j.prz.fi, j.prz.se, j.c);
		for(int j = 0; j <= k && drz[1].t[j].fi <= k; ++j) wyn[max(1, drz[1].t[j].fi)] += (ll)drz[1].t[j].se;
	}
	
	wyn[1] -= (((ll)n2)*((ll)(n2-1)))>>1ll;
	for(int i = 1; i <= k; ++i) cout << wyn[i] << " ";
	return 0;
}