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 #include using namespace std; int n,k; int bricks[2][100001]; bool visited[2][100001]; long long results[100001]; int neighbors[3][200001]; int totalgroups = 0; int group[200001]; int rank[200001]; int num_of_groups(int, int); int find(int x) { if (group[x] == -1) { return -1; } int res = x; if (group[x] != x) { res = find(group[x]); group[x] = res; } return res; } void funion(int x, int y) { // unify groups of x and y int rx = find(group[x]); int ry = find(group[y]); if (rank[x] > rank[y]) { group[ry] = rx; } else if (rank[x] < rank[y]) { group[rx] = ry; } else if (rx != ry) { group[ry] = rx; rank[rx] += 1; } } int main() { scanf("%d %d", &n, &k); scanf("%d", &bricks[0][0]); for (int i = 1; i < n; ++i) { scanf("%d", &bricks[0][i]); neighbors[1][bricks[0][i]] = bricks[0][i-1]; // left neigh neighbors[2][bricks[0][i-1]] = bricks[0][i]; // i is left's right neigh } neighbors[1][bricks[0][0]] = bricks[0][n-1]; neighbors[2][bricks[0][n-1]] = bricks[0][0]; scanf("%d", &bricks[1][0]); neighbors[0][bricks[1][0]] = bricks[0][0]; neighbors[0][bricks[0][0]] = bricks[1][0]; for (int i = 1; i < n; ++i) { scanf("%d", &bricks[1][i]); neighbors[0][bricks[1][i]] = bricks[0][i]; neighbors[0][bricks[0][i]] = bricks[1][i]; neighbors[1][bricks[1][i]] = bricks[1][i-1]; // left neigh neighbors[2][bricks[1][i-1]] = bricks[1][i]; // i is left's right neigh } neighbors[1][bricks[1][0]] = bricks[1][n-1]; neighbors[2][bricks[1][n-1]] = bricks[1][0]; // neighbors[0][n] is vertical neighbor of n if all tiles are lit // neighbors[1][n] is horizontal left neighbor of n if all tiles are lit // neighbors[2][n] is horizontal right neighbor of n if all tiles are lit for (int i = 1; i <= 2*n; ++i) { // initiate find-union here for (int j = 1; j <= 2*n; ++j) { group[j] = -1; } totalgroups = 0; for (int j = i; j <= 2*n; ++j) { // we start with [i,i] interval (only 1 lit tile) and add tiles one by one group[j] = j; rank[j] = 0; totalgroups += 1; for (int nn = 0; nn < 3; ++nn) { int neigh = neighbors[nn][j]; int ng = find(neigh); int myg = find(j); if (ng == -1) { // printf("Neighbor %d dark, continuing\n", neigh); continue; } // else { // printf("Neighbor %d lit, checking\n", neigh); // } if (ng != myg) { totalgroups -= 1; funion(neigh, j); } } // printf("%d %d: %d groups\n", i, j, totalgroups); results[totalgroups] += 1; } } for (int i = 1; i <= k; ++i) { printf("%lld ", results[i]); } printf("\n"); return 0; }