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
#include <cstdio>
#include <cstring>

const int C = 1;
const int Z = 2;
const int NN = 200200;

inline int cast(char color) { return color == 'C' || color == C ? C : Z; }
inline int flip(int color) {
  switch (color) {
  case C:
    return Z;
  case Z:
    return C;
  }
  return color;
}
inline char up(char c) { return c == C ? 'C' : 'Z'; }

int compute(const char *input, int len) {
  int **opts = new int *[len];
  for (int i = 0; i < len; ++i) {
    opts[i] = new int[len];
    memset(opts[i], 0, len * sizeof(int));
  }

  for (int b = 0; b < len; ++b) {
    opts[b][b] = input[b];
    for (int a = b - 1; a >= 0; --a) {
      for (int m = a; m < b; ++m) {
        opts[a][b] |= flip(opts[a][m] & opts[m + 1][b]);
      }
    }
  }
  int ret = opts[0][len - 1];

  for (int i = 0; i < len; ++i) {
    delete[] opts[i];
  }
  delete[] opts;
  return ret;
}

int options(char *word, int offset) {
  for (int i = offset; word[i]; ++i) {
    if (word[i] != 'N') {
      word[i] = cast(word[i]);
    } else {
      word[i] = C;
      int a = options(word, i + 1);
      word[i] = Z;
      int b = options(word, i + 1);
      word[i] = 'N';
      return a + b;
    }
  }
  bool found = compute(word, strlen(word));
  return found ? 1 : 0;
}

char word[NN];
char word2[NN];

int call() {
  strcpy(word2, word);
  return options(word2, 0);
}

int main() {
  int N, Q;
  scanf("%d%d%s", &N, &Q, word);

  int p;
  char r;
  printf("%d\n", call());
  for (int i = 0; i < Q; ++i) {
    scanf("%d %c", &p, &r);
    word[p - 1] = r;
    printf("%d\n", call());
  }
  return 0;
}