3893: 黄老师的回文树节点

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

黄老师有一棵完全二叉树，这棵树一共有 $n$ 个节点，编号为 $1 \sim n$，每个节点上有一个小写字母

其中根节点编号是 $1$，$i$ 节点的左孩子是 $i * 2$，右孩子是 $i * 2 + 1$

现在黄老师提出了一个问题，对于编号为 $i$ 的节点，如果它以及它所有子树上的字母能够组成一个回文字符串，那么黄老师就认为这个节点是 `回文树节点`

黄老师的算法水平不高，所以他认为，只要子树上的字母能够在任意排列的情况下成为回文字符串，那么就可以了

现在黄老师想知道这棵树有几个 `回文树节点`

但是石老师又给黄老师加了一个难题，他想让这道题变成一个动态的题目——增加多次修改操作

所以接下来石老师会给出 $q$ 次修改，每次修改一个节点编号为 $x$ 的节点，将这个节点上的字母修改为 $c$

在每次修改以后，石老师希望知道现在这棵树上有多少个 `回文树节点`

P.S. 回文字符串是指从左往右念和从右往左念一样的字符串，比如 `abcba`,`aaeebeeaa`,`xxyyxx`

输入

输入第一行包含两个正整数 $n,q$，表示节点数量和操作次数。

接下来一行一个长度为 $n$ 的字符串，第 $i$ 个字符表示第 $i$ 个节点上的初始字母。

接下来 $q$ 行，每行一个正整数 $x$ 一个字符 $c$，表示将节点 $x$ 上的字母修改为 $c$。
对于 $30\%$ 的数据，满足 $1 \leq n,q \leq 20$

对于 $70\%$ 的数据，满足 $1 \leq n,q \leq 1000$

对于 $100\%$ 的数据，满足 $1 \leq n,q \leq 100000$


输出

输出第一行一个整数表示一开始这棵树有几个 `回文树节点`

接下来 $q$ 行，每行表示在进行石老师要求的修改操作后，现在这棵树有几个 `回文树节点`

样例输入 复制 

4 2
aabc
1 b
2 c

样例输出 复制 

2
2
4

提示

这棵树一开始是这样的：
```
      a
     / \
    a   b
   /
  c
```
所以一开始只有 $3,4$ 两个节点是 `回文树节点`

1. 修改 $1$ 号节点为 $b$
```
      b
     / \
    a   b
   /
  c
```
依旧只有 $3,4$ 两个节点是 `回文树节点`

2. 修改 $2$ 号节点为 $c$
```
      b
     / \
    c   b
   /
  c
```
此时 $1,2,3,4$ 节点都是 `回文树节点`
$1$ 号节点的子树可以构成 $bccb$ 这个回文字符串
$2$ 号节点的子树可以构成 $cc$ 这个回文字符串
$3$ 号节点的子树可以构成 $c$ 这个回文字符串
$4$ 号节点的子树可以构成 $b$ 这个回文字符串


来源/分类

提交提交记录统计露一手!