[Ynoi2011] 遥远的过去

题目背景

小学六年级的时候学了JAVA,写了个小游戏,大概是把我奥数老师的头弹飞出去拿来打青蛙的,看来我小时候就懂膜蛤和P头了。 现在感觉当时很多东西没理解,都在乱写,程序里面全是if,就这样还是写出来了,还拿了个科创大赛一等奖(可以加5分中考分的,可不算很野鸡!) 所以一直感觉我其实是很喜欢做一些有创造性的东西的,这点之后也会体现出来。 上了初中,因为之前学过点小学奥数,同时也有学一些数学竞赛的东西,所以感觉老师讲课都很平凡,没什么兴趣。 第一次接触到了信息学竞赛,当时感觉还是挺有趣的,不过也没怎么认真学。 学校里面有OI的培训,但由于学校里面在教Pascal,我当时已经学过JAVA了,自然觉得这个语言很落后,垃圾,所以也没怎么听课,印象中我去参加个选拔考试,有个鸡兔同笼的题,我写了个解方程被扣分了,老师给的正解是 while( a-- ) b++ 这样的东西,然后就决定不去了。 初二考了一次NOIP普及组,当时只拿了120,第二题是个表达式求值,我写了很久很久都一直挂,然后就凉凉了。 考完之后得知班上几个同学考了全省前10,感觉他们好强,当时还是很有好胜心的,于是决定好好学OI,初三打爆他们。 初三的时候考了295,被两个当时初二的小朋友打爆了,不过我是初三里面最高分( 那两个小朋友好像现在都去茶园了,果然是神仙。 感觉初中还是挺好玩的,虽然天天和毒瘤老师斗智斗勇,但还是很有趣。 【记得配图,内容:写的小游戏的截图,还有noip的成绩】 由于这是Ynoi,不是出题人拿来写奇怪的文字的地方,所以你需要做一个数据结构题:

题目描述

小 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-匹配 的次数。

输入输出样例

输入样例 #1

5 3 2
11 7 5 3 2
3 2 1
2 5
1 6

输出样例 #1

0
3

说明

Idea:nzhtl1477,Solution:nzhtl1477,Code:nzhtl1477,Data:nzhtl1477( partially uploaded ) ### 样例 1 解释 在第一次修改后,$\{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$。