#P18060. AND Components

AND Components

AND Components

给定长度为 NN 的整数数组 AA,以及两个长度为 NN 的二进制字符串 L,RL,R。

根据当前的 A,L,RA,L,R,构造一个有 NN 个顶点的无向图。对于每个顶点 ii,按以下规则至多加入两条边:

  • 如果 Li=1L_i=1,在所有满足 j<ij<i 且 (Aj&Ai)>0(A_j\mathbin{\&}A_i)>0 的下标中,选择最大的 jj,加入边 (i,j)(i,j)。如果不存在这样的 jj,则不加入这条边。
  • 如果 Ri=1R_i=1,在所有满足 j>ij>i 且 (Aj&Ai)>0(A_j\mathbin{\&}A_i)>0 的下标中,选择最小的 jj,加入边 (i,j)(i,j)。如果不存在这样的 jj,则不加入这条边。

其中 &\& 表示按位与。边是无向的;同一条边被重复加入不影响连通性。某个顶点的开关为 00,不妨碍其他顶点主动向它连边。

有 QQ 次修改,每次修改 A,L,RA,L,R 中的一个元素。请在所有修改之前,以及每次修改之后,求当前图的连通块数量。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据第一行两个整数 N,QN,Q;第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N;第三、四行分别为二进制字符串 L,RL,R。

接下来 QQ 行,每行一项操作,格式为以下三者之一:

  • A i x:令 Ai=xA_i=x。
  • L i x:令 Li=xL_i=x。
  • R i x:令 Ri=xR_i=x。

输出格式

每组数据输出 Q+1Q+1 行。第一行为初始答案,之后依次为各次修改后的答案。

数据范围

1≤T≤1041\le T\le10^4,1≤N,Q≤1051\le N,Q\le10^5,0≤Ai≤1060\le A_i\le10^6。操作下标满足 1≤i≤N1\le i\le N;修改 AA 时 0≤x≤1060\le x\le10^6,修改 L,RL,R 时 x∈{0,1}x\in\{0,1\}。

跨所有测试用例,∑N\sum N、∑Q\sum Q 各自不超过 10510^5。

样例

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