[R34F]子串数量 - 代码源竞赛平台

时空限制

2S / 512M

题目描述

给定两个长度为 $n$ 的字符串 $s$ 和 $t$，它们都只包含小写英文字母。

你需要处理 $q$ 次操作和查询。操作分为以下三种类型：

1. 1 i c：将字符串 $s$ 的第 $i$ 个字符修改为 $c$。
2. 2 i c：将字符串 $t$ 的第 $i$ 个字符修改为 $c$。
3. 3 l r：查询满足 $l \le i \le j \le r$ 且 $s$ 的子串 $s[i ,\cdots , j]$ 按字典序严格小于 $t$ 的子串 $t[i ,\cdots , j]$ 的数对 $(i, j)$ 的数量。

字典序定义：对于两个等长的字符串 $A$ 和 $B$，$A$ 的字典序小于 $B$，当且仅当存在一个下标 $k$，使得对于所有 $p < k$，$A_p = B_p$，且 $A_k < B_k$。

格式

输入格式

第一行包含两个正整数 $n, q$，分别表示字符串的长度和操作与查询的总数。

第二行包含一个长度为 $n$ 的字符串 $s$。

第三行包含一个长度为 $n$ 的字符串 $t$。

接下来 $q$ 行，每行描述一个操作或查询，格式如下：

• 1 i c：表示一个类型为 $1$ 的操作，$1 \le i \le n$，$c$ 是一个小写英文字母。
• 2 i c：表示一个类型为 $2$ 的操作，$1 \le i \le n$，$c$ 是一个小写英文字母。
• 3 l r：表示一个类型为 $3$ 的查询，$1 \le l \le r \le n$。

输出格式

对于每个类型为 $3$ 的查询，输出一行，包含一个整数，表示查询的结果。

样例

样例输入 #1

5 3
ababa
acaca
3 1 5
1 3 c
3 1 5

样例输出 #1

12
10

数据规模

对于 $20\%$ 的数据，$1 \leq n , q \leq 50$。

对于 $50\%$ 的数据，$1 \le n, q \le 500$。

对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10^5$。字符串 $s$ 和 $t$ 仅包含小写英文字母（a-z）。