#P18060. AND Components
AND Components
AND Components
给定长度为 的整数数组 ,以及两个长度为 的二进制字符串 。
根据当前的 ,构造一个有 个顶点的无向图。对于每个顶点 ,按以下规则至多加入两条边:
- 如果 ,在所有满足 且 的下标中,选择最大的 ,加入边 。如果不存在这样的 ,则不加入这条边。
- 如果 ,在所有满足 且 的下标中,选择最小的 ,加入边 。如果不存在这样的 ,则不加入这条边。
其中 表示按位与。边是无向的;同一条边被重复加入不影响连通性。某个顶点的开关为 ,不妨碍其他顶点主动向它连边。
有 次修改,每次修改 中的一个元素。请在所有修改之前,以及每次修改之后,求当前图的连通块数量。
输入格式
第一行一个整数 ,表示测试用例数。
每组数据第一行两个整数 ;第二行 个整数 ;第三、四行分别为二进制字符串 。
接下来 行,每行一项操作,格式为以下三者之一:
A i x:令 。L i x:令 。R i x:令 。
输出格式
每组数据输出 行。第一行为初始答案,之后依次为各次修改后的答案。
数据范围
,,。操作下标满足 ;修改 时 ,修改 时 。
跨所有测试用例,、 各自不超过 。
样例
2
5 4
1 2 4 1 1
10101
11011
A 1 4
A 1 1
L 2 0
A 5 3
4 4
1 1 1 0
1111
1111
A 2 2
R 1 0
L 4 0
A 4 1
3
3
3
3
2
2
3
3
3
2