#D. Yet Another 字母矩阵问题

    传统题 3000ms 512MiB

Yet Another 字母矩阵问题

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有一个 nnmm 列的小写字母矩阵,你需要把这个矩阵切成两个连通的部分(分别至少一个字母),其中一部分的所有字母都小于另一部分的所有字母,求方案数。

但是这个问题太简单了,所以在此基础上有 qq 次操作,分为两种:

  • c x yc\ x\ y 修改第 xxyy 列的字符为 cc,并求出当前的方案数。这个操作是临时的,也就是回答结束后操作就恢复。
  • + s\texttt{+}\ s+\texttt{+} 的 ASCII 为 4343),新增一列,新列第 xx 行字符为 sxs_x,并求出当前的方案数。这个操作是永久的,会影响之后的询问。

输入格式

输入有三个正整数 n,m,qn,m,q,分别表示行数、列数和询问数。

之后 nn 行,每行 mm 个字符,表示最开始的字符矩阵。

ansians_i 为第 ii 次操作之后的方案数。特别地,ans0ans_0 为初始方案数,ans1=0ans_{-1}=0

之后 qq 行,每行一个操作,为下面两种格式之一:

  • c x yc\ x'\ y',表示一次修改操作,假如当前是第 ii 次操作,那么真实 x=xansi1x=x'\oplus ans_{i-1}y=yansi2y=y'\oplus ans_{i-2},其中 \oplus 是按位异或。
  • + s\texttt{+}\ s,表示一次增加操作。该操作不加密。

输出格式

输出 ans0,ans1,,ansqans_0,ans_1,\ldots, ans_q,每个数一行。

样例 #1

样例输入 #1

3 3 6
aba
aee
eff
a 3 2
e 3 0
f 0 0
b 3 3
e 0 3
+ aaa

样例输出 #1

2
2
1
0
1
3
2

样例 #2, #3, #4, #5, #6

点我下载大样例

样例 262\sim 6 分别满足测试点 6,8,11,13,216,8,11,13,21 的限制。

提示

【样例解释】

一开始有如下两种划分方案(分为粗体和非粗体两块):

方案 1 a b a 方案 2 a b a
a e a e
e f e f

第一次询问将第 11 行第 22 列修改成 a

第二次询问将第 11 行第 22 列修改成 e

第三次询问将第 11 行第 22 列修改成 f

第四次询问将第 33 行第 22 列修改成 b

第五次询问将第 11 行第 33 列修改成 e

接下来新增一列,现在矩阵为:

abaa
aeea
effa

【数据范围】

Testcases nn\le mm\le qq\le + 数量 \le 特殊性质
11 10001000 55 00
22 22
33 22
44 44 44 00
55 33 22
6,76,7 400400 10001000 00 字符只有 a,b
8,9,108,9,10
11,1211,12 10510^5 输入矩阵第奇数列等于后一列
13,1413,14 询问点左侧和上方字符相同
151815\sim 18
19,2019,20 10001000 询问点左侧和上方字符相同
212521\sim25

对于全体数据,保证 1n4001\le n\le 4001m10001\le m\le 10001q1051\le q\le 10^5,其中加列不超过 10001000 次,所有字符串都只有小写字母。

[YDRG#003 Div. 1] YDSP-S 组赛前模拟 · 云斗杯十月 Golden Round

已参加
状态
已结束 (已参加)
规则
OI
题目
6
开始于
2023-10-14 8:30
结束于
2023-10-14 13:30
持续时间
5 小时
主持人
参赛人数
287