#951. [yLOI2019] 棠梨煎雪

[yLOI2019] 棠梨煎雪

题目描述

扶苏正在听《棠梨煎雪》的时候,

https://www.luogu.org/space/show?uid=61795
训队作业题](http://uoj.ac/problem/425):我切了这集训队题,辣鸡扶苏快过来做题。扶苏定睛一看,这不 s* 题嘛,写了一发交上去才发现自己看错题目了。但是写完的代码不能浪费,于是就有了这道题。

歌词中的主人公与她的朋友一年会有一次互相写信给对方,一共通信了 mm 年。为了简化问题,我们认为她们每封信的内容都是一条二进制码,并且所有二进制码的长度都是 nn。即每封信的内容都是一个长度为 nn 的字符串,这个字符串只含字符 0 或 1。

这天她拿出了朋友写给她的所有信件,其中第 ii 年的写的信件编号为 ii。由于信件保存时间过久,上面有一些字符已经模糊不清,我们将这样的位置记为 ?,? 字符可以被解释为 0 或 1。由于她的朋友也是人,符合人类的本质,所以朋友在一段连续的时间中书写的内容可能是相同的。现在她想问问你,对于一段连续的年份区间 [l,r][l,r] 中的所有信件,假如朋友在这段时间展示了人类的本质,所写的是同一句话,那么这一句话一共有多少种可能的组成。也即一共有多少字符串 SS,满足在这个区间内的所有信件的内容都可能是 SS。

一个长度为 nn 的只含 0,1,? 的字符串 AA 可能是一个字符串 BB 当且仅当 BB 满足如下条件:

  • BB 的长度也是 nn 。
  • BB 中只含字符 0,1。
  • AA 中所有为 0 的位置在 BB 中也是 0。
  • AA 中所有为 1 的位置在 BB 中也是 1。
  • AA 中为 ? 的位置在 BB 中可以为 0 也可以是 1。

同时她可能会突然发现看错了某年的信的内容,于是她可能会把某一年的信的内容修改为一个别的只含 0,1,? 的长度为 nn 的字符串。

输入格式

每个输入文件中都有且仅有一组测试数据。

输入数据第一行为三个用空格隔开的整数,分别代表代表字符串长度 nn,字符串个数 mm 和操作次数 qq。

下面 mm 行,每行是一个长度为 nn 的字符串,第 (i+1)(i + 1) 行的字符串 sis_i 代表第 ii 年信的内容。

下面 qq 行,每行的第一个数字是操作编号 optopt。

  • 如果 opt=0opt=0,那么后面接两个整数 [l, r][l,~r],代表一次查询操作。
  • 如果 opt=1opt=1,那么后面接一个整数 pospos,在一个空格后会有一个长度为 nn 的字符串 tt,代表将第 pospos 个字符串修改为新的字符串 tt。

输出格式

为了避免输出过大,请你输出一行一个数代表所有查询的答案异或和对 00 取异或的结果。

样例

3 3 5
010
0?0
1?0
0 1 2
0 2 3
1 3 0??
0 2 3
0 1 3
2

题目来源:洛谷 P5522