遥远的过去 - المسألة

题目描述

小 F 决定设计出一种字符集超大的语言——Z 语言，哪怕有时额外的字符并没有什么用。

这种语言的特点是：

字符集非常大，甚至可能有 $2147483648(2 ^ {31})$ 种字符；
每个单词由一系列两两不同的字符组成；
字符既能比较相同和不同，也能比较大小，因此之后我们用数字来表示 Z 语言中稀奇古怪的字符；
两个看起来完全不同的单词也可能是同一个单词，因为：只要两个单词中第 K 大的字符所在的位置相同，那么其实就是本质上相同的单词。例如 $\{1, 2, 3, 4, 5\}$ 与 $\{2, 3, 23, 233, 23333\}$ 是相同的。（所以你可以用 Z 语言很方便地加密信息！）

现在，小 F 打算将 Z 语言应用到实际中。比如，他点开了一道电脑里的算法题：

给定两个字符串 $A, B$ ，求 $B$ 作为子串在 $A$ 中被匹配的次数。

小 F 当然知道这是一个可以用 KMP 解决的基础题。但是，他在用 Z 语言的匹配实现 Z-KMP 的时候遇到了问题，你能帮帮他吗？

为了验证你是不是真的明白小 F 在说什么，小 F 会修改 $B$ 串很多次来问你。可不准偷懒哦！

你的程序需要支持的操作详见输入输出格式。

输入第一行两个整数 $n, m, q(1 \leq n, m, q \leq 10 ^ 5)$，表示 $A, B$ 串的长度以及操作次数。

第二行 $n$ 个非负整数，第 $i$ 个表示 $A$ 串的第 $i$ 个字符 $A_i$ $(0 \leq A_i \leq 2147483647=2 ^ {31} - 1)$。

第三行 $m$ 个非负整数，第 $i$ 个表示 $B$ 串的第 $i$ 个字符 $B_i$ $(0 \leq B_i \leq 2147483647=2 ^ {31} - 1)$。

接下来 $q$ 行，每行两个正整数 $x_i, c_i$ $(1 \leq c_i \leq 2147483647=2 ^ {31} - 1)$，表示将 $B$ 串 $x_i$ 位置上的字符由 $B_{x_i}$ 改为 $c_i$。

数据保证，任意时刻 $A$ 和 $B$ 均是满足前述要求的合法 Z 字符串。

在每次修改完成后，请输出 $B$ 作为子串在 $A$ 中被 Z-匹配的次数。

0
3

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477( partially uploaded )

在第一次修改后，$\{3, 5, 1\}$ 并不能被任何一个 $A$ 中的子串匹配上。

在第二次修改后，$\{6, 5, 1\}$ 能被 $A$ 中所有长度为 $3$ 的串匹配上，原因是 A 是单调减的，而 B 也是单调减的，因此 $A$ 中所有长度为 $3$ 的串与 $B$ 排名相同的处于相同位置。

子任务 $1(31 \mathrm{pts}) : n, m \leq 100, q \leq 1000$；

子任务 $2(41 \mathrm{pts}) : n, m \leq 1000, q \leq 5 \times 10 ^ 4$；

子任务 $3(78 \mathrm{pts}) : n, m, q \leq 10 ^ 5$。