QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 500 MB Total points: 150
[+5]

# 7467. 遥远的过去

Statistics

题目描述

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

这种语言的特点是:

  • 字符集非常大,甚至可能有 2147483648(231) 种字符;

  • 每个单词由一系列两两不同的字符组成;

  • 字符既能比较相同和不同,也能比较大小,因此之后我们用数字来表示 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(1n,m,q105),表示 A,B 串的长度以及操作次数。

第二行 n 个非负整数,第 i 个表示 A 串的第 i 个字符 Ai (0Ai2147483647=2311)

第三行 m 个非负整数,第 i 个表示 B 串的第 i 个字符 Bi (0Bi2147483647=2311)

接下来 q 行,每行两个正整数 xi,ci (1ci2147483647=2311),表示将 Bxi 位置上的字符由 Bxi 改为 ci

数据保证,任意时刻 AB 均是满足前述要求的合法 Z 字符串。

输出格式

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

样例 #1

样例输入 #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(31pts):n,m100,q1000

子任务 2(41pts):n,m1000,q5×104

子任务 3(78pts):n,m,q105