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 <cstdio>
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;
}