← 返回题目列表

AtCoder · pakencamp_2023_day3_h

H. 腐烂

中文机器翻译题面 查看原题

配点 : 100 点

問題文

非空字符串 X 和非负整数 定义 K ,\operatorname{rot}(X,K) 如下。 将

  • X 的第一个字符移动到末尾的操作是 K 次结果得到的字符串。

等长的非空字符串 按字典顺序小于 X, Y , 如果对满足f(X, Y) 如下。 将

  • 0\leq i\lt|X| 和 \operatorname{rot}(X,i) 的 \operatorname{rot}(Y,i) 的整数 i 的数量。

正整数 N 长度是 一个字符串 N 给出了 S,T 。下面 2 查询类型总数 您将获得 Q 碎片,请处理它们。

  • 查询 1: 整数 L,R 。 表示S 的 合并 L 从第一个字符开始 R 提取到第一个字符得到的字符串是 作为 S'、T 的 合并 L 从第一个字符开始 R 提取到第一个字符得到的字符串是 作为 T' , 查找f(S',T') 。
  • 查询 2: 整数 X, Y 和小写字母 C 。 表示X = 1 什么时候 S 的 合并 Y 第一个字母 替换为 C 。X = 2 什么时候 T 的 合并 Y 第一个字母 替换为 C 。

制約

  • 1\leq N\leq 2\times 10^{5}
  • S 和 按字典顺序比较 T 是小写字母的长度 N 字符串
  • 1\leq Q\leq 2\times 10^{5}
  • 查询 1 , 当我输入1\leq L\leq R\leq N
  • 查询 2 , 当我输入X\in\lbrace 1,2\rbrace,1\leq Y\leq N 和C 是一个小写字母 表示第

入力

输入将以以下格式从标准输入给出。

N
S
T
Q
\mathrm{Query}_{1}
\mathrm{Query}_{2}
\vdots
\mathrm{Query}_{Q}

但是, 运算前设定中包含的\mathrm{Query}_{i} 是 i 个查询的内容。每个查询的内容按以下格式给出:

  • i 第一个查询是查询 1 什么时候
1 L R
  • i 第一个查询是查询 2 什么时候
2 X Y C

出力

每个查询 回答 1 请在 1 行输出。 它应该打印


入力例 1

9
dacbyzyzx
dcabzyzyx
6
1 2 4
1 5 9
2 1 1 z
1 1 1
2 2 9 a
1 6 9

出力例 1

2
3
0
1

1 个查询。S'=\mathtt{acb},T'=\mathtt{cab} 和f(S',T') 。

  • \operatorname{rot}(S',0)=\mathtt{acb},\operatorname{rot}(T',0)=\mathtt{cab}
  • \operatorname{rot}(S',1)=\mathtt{cba},\operatorname{rot}(T',1)=\mathtt{abc}
  • \operatorname{rot}(S',2)=\mathtt{bac},\operatorname{rot}(T',2)=\mathtt{bca}

所以这个查询的输出是 2 。


入力例 2

20
pilrajvvuwrcxvbchgyf
pitlabnvzyrmoveahgyr
20
2 2 3 l
2 2 3 l
1 3 17
2 1 6 b
1 1 13
1 19 20
1 8 14
1 2 16
2 1 9 c
2 2 19 x
2 1 20 r
2 2 9 c
1 7 7
1 11 13
1 10 20
1 9 11
2 2 1 b
1 6 16
2 1 1 w
2 1 1 q

出力例 2

7
5
2
6
7
0
2
6
3
7