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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<pair<int, int>, pair<int, int> > rect_t;

int main () {
	int n, k, x;
	scanf("%d %d\n", &n, &k);
	vector<int> r1, r2;
	for (int i = 0; i < n; ++i) {
		scanf("%d", &x);
		r1.push_back(x);
	}
	for (int i = 0; i < n; ++i) {
		scanf("%d", &x);
		r2.push_back(x);
	}
	vector<rect_t> rects;
	for (int i = 0; i < n; ++i) {
		int a = r1[i];
		int b = r1[(i + 1) % n];
		int c = r2[i];
		int d = r2[(i + 1) % n];
		if (a > c) {
			int tmp = a;
			a = c;
			c = tmp;
			tmp = b;
			b = d;
			d = tmp;
		}
		int l1, r1, b1, t1, l2, r2, b2, t2, l3, r3, b3, t3;
		bool third = false;
		if ((a < b) && (b < c) && (c < d)) {
			l1 = 1; r1 = a; b1 = a; t1 = b - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = d - 1;
		}
		if ((a < b) && (b < d) && (d < c)) {
			l1 = 1; r1 = a; b1 = a; t1 = b - 1;
			l2 = d + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((a < c) && (c < b) && (b < d)) {
			l1 = 1; r1 = a; b1 = a; t1 = b - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = d - 1;
		}
		if ((a < c) && (c < d) && (d < b)) {
			l1 = 1; r1 = a; b1 = a; t1 = d - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = d - 1;
		}
		if ((a < d) && (d < b) && (b < c)) {
			l1 = 1; r1 = a; b1 = a; t1 = b - 1;
			l2 = d + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((a < d) && (d < c) && (c < b)) {
			l1 = 1; r1 = a; b1 = a; t1 = c - 1;
			l2 = d + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((b < a) && (a < c) && (c < d)) {
			l1 = b + 1; r1 = a; b1 = a; t1 = d - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = d - 1;
		}
		if ((b < a) && (a < d) && (d < c)) {
			l1 = b + 1; r1 = a; b1 = a; t1 = c - 1;
			l2 = d + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((b < d) && (d < a) && (a < c)) {
			l1 = b + 1; r1 = a; b1 = a; t1 = c - 1;
			l2 = d + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((d < a) && (a < b) && (b < c)) {
			l1 = 1; r1 = a; b1 = a; t1 = b - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		if ((d < a) && (a < c) && (c < b)) {
			l1 = 1; r1 = a; b1 = a; t1 = c - 1;
			l2 = a + 1; r2 = c; b2 = c; t2 = 2 * n;
			l3 = d + 1; r3 = a; b3 = c; t3 = b - 1;
			third = true;
		}
		if ((d < b) && (b < a) && (a < c)) {
			l1 = b + 1; r1 = a; b1 = a; t1 = 2 * n;
			l2 = a + 1; r2 = c; b2 = c; t2 = 2 * n;
		}
		rects.push_back(make_pair(make_pair(l1, b1), make_pair(r1, t1)));
		rects.push_back(make_pair(make_pair(l2, b2), make_pair(r2, t2)));
		if (third) {
			rects.push_back(make_pair(make_pair(l3, b3), make_pair(r3, t3)));
		}
	}
	vector<pair<int, pair<char, pair<int, int> > > > q;
	for (int i = 1; i <= 2 * n; ++i) {
		q.push_back(make_pair(i, make_pair(3, make_pair(0, 0))));
	}
	for (int i = 0; i < rects.size(); ++i) {
		q.push_back(make_pair(rects[i].first.first, make_pair(1, make_pair(rects[i].first.second, rects[i].second.second))));
		q.push_back(make_pair(rects[i].second.first + 1, make_pair(2, make_pair(rects[i].first.second, rects[i].second.second))));
	}
	sort(q.begin(), q.end());
	vector<int> col(2 * n + 1, 0);
	vector<int> cnts(rects.size() + 8, 0);
	cnts[0] = 2 * n;
	vector<int64_t> totals(k + 2, 0);
	for (int i = 0; i < q.size(); ++i) {
		pair<int, pair<char, pair<int, int> > > ev = q[i];
		if (ev.second.first == 1) {
			for (int j = ev.second.second.first; j <= ev.second.second.second; ++j) {
				--cnts[col[j]];
				++col[j];
				++cnts[col[j]];
			} 
		}
		if (ev.second.first == 2) {
			for (int j = ev.second.second.first; j <= ev.second.second.second; ++j) {
				--cnts[col[j]];
				--col[j];
				++cnts[col[j]];
			} 
		}
		if (ev.second.first == 3) {
			for (int j = 0; j <= k; ++j) {
				totals[j] += cnts[j];
			}
		}
	}
	printf("%lld ", totals[0] + totals[1] - (int64_t)n * (2 * n - 1));
	for (int i = 2; i <= k; ++i) {
		printf("%lld ", totals[i]);
	}
	printf("\n");
	return 0;
}