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 #include "bits/stdc++.h" // Ignacy Boehlke using namespace std; // XIII LO Szczecin templateostream&operator<<(ostream&os,pairp){return os<<'{'<auto operator<<(ostream&os,T v)->decltype(v.end(),os){os<<'{';int i=0;for(auto e:v)os<<(", ")+2*!i++< vec; Str(vector&& _vec) : n(ssize(_vec)), vec(_vec) {} void set(int i, int val) {vec[i] = val;} vector get(int i) { vector res(k + 1); int s = 0; FOR(j, i, n - 1) { s += vec[j]; if (s <= k) ++res[s]; } return res; } }; int main() { init(); cin.tie(0)->sync_with_stdio(0); int n; cin >> n >> k; int N = 2 * n; vector canvas(N), pos(N); int id = 0; REP(i, 2) { REP(j, n) { cin >> canvas[id]; pos[--canvas[id]] = id; ++id; } } #define OPP(x) (x < n ? x + n : x - n) #define NXT(x) (x + 1 == n ? 0 : (x + 1 == N ? n : x + 1)) #define PRV(x) (x - 1 == -1 ? n - 1 : (x - 1 == n - 1 ? N - 1 : x - 1)) auto cnt = [&](int x, int l) { int p = pos[x]; vector ng = {NXT(p), NXT(OPP(p)), OPP(p), PRV(OPP(p)), PRV(p)}; int ngmp = 0; REP(i, 5) ngmp |= ((canvas[ng[i]] < x && l <= canvas[ng[i]]) << i); return diff[ngmp]; }; vector vec(N); REP(i, N) vec[i] = cnt(i, 0); //LOG(vec); Str str(std::move(vec)); auto updval = [&](int x, int l) { int d = cnt(x, l); str.set(x, d); }; vector res(k + 1); REP(i, N) { //LOG(str.vec); vector r = str.get(i); LOG(r); res[1] += r[0]; FOR(j, 1, k) res[j] += r[j]; int p = pos[i]; vector ng = {NXT(p), NXT(OPP(p)), OPP(p), PRV(OPP(p)), PRV(p)}; for (int el : ng) if (canvas[el] > i) updval(canvas[el], i + 1); } FOR(i, 1, k) cout << res[i] << ' '; cout << '\n'; }