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
#include <cstdio>
#include <map>
#include <unordered_map>

using std::map;
using std::unordered_map;

const int NN = 100100;
const int ROWS = 2;

int data[NN][ROWS];

typedef int Color;

class UnionSet {
  UnionSet *parent;

public:
  UnionSet():parent(this){}
  void init() { parent = this; }
  bool isDisjoint(UnionSet *other) { return repr() != other->repr(); }
  void joint(UnionSet *other) { other->repr()->parent = this; }

private:
  UnionSet *repr() {
    if (parent == this) {
      return this;
    } else {
      return parent = parent->repr();
    }
  }
};

struct Adj {
  Color a[3];
};

unordered_map<Color, Adj> *compute_adj(int Cols) {
  unordered_map<Color, Adj> *ret = new unordered_map<int, Adj>;
  for (int r = 0; r < ROWS; ++r) {
    for (int c = 0; c < Cols; ++c) {
      Adj x = {.a = {data[c][ROWS - r - 1], data[(c + 1) % Cols][r], data[(c + Cols - 1) % Cols][r]}};
      ret->insert({data[c][r], x});
    }
  }
  return ret;
}

map<int, int> compute(int colors, int K, unordered_map<Color, Adj> *data) {
  map<int, int> res;
  for (int i = 1; i <= K; ++i) {
    res[i] = 0;
  }
  unordered_map<Color, UnionSet *> sets;
  int count;
  for (Color l = 1; l <= colors; ++l) {
    for (auto p : sets) {
      delete p.second;
    }
    sets.clear();
    count = 0;
    for (Color r = l; r <= colors; ++r) {
      UnionSet *cur = new UnionSet();
      sets[r] = cur;
      count++;
      for (Color c : (*data)[r].a) {
        auto res = sets.find(c);
        if (res != sets.end()) {
          if (cur->isDisjoint(res->second)) {
            cur->joint(res->second);
            --count;
          }
        }
      }
      if (count <= K) {
        res[count] += 1;
      }
    }
  }
  return res;
}

int main() {
  int COLS, K;
  scanf("%d%d", &COLS, &K);

  for (int r = 0; r < ROWS; ++r) {
    for (int c = 0; c < COLS; ++c) {
      scanf("%d", &data[c][r]);
    }
  }

  unordered_map<int, Adj> *adj = compute_adj(COLS);

  map<int, int> res = compute(2 * COLS, K, adj);
  for (auto p : res) {
    printf("%d ", p.second);
  }
  printf("\n");

  delete adj;
  return 0;
}