#C2023M. 造CPU

造CPU

希望你在[广告位招租]中,找到答案。

题目描述

谷米莱莉娅的朋友小衣最近在深入学习计算机体系结构,迷上了CPU。她花了一个学期深入研究了[广告位招租]的[广告位招租]架构,然后决定开始自己造CPU。她的CPU是一个非常精致而简约的结构,也就是说它是一个有nn个结点的链,按顺序将结点编号为1,2,,n1,2,\dots,n。CPU的结点类型有两种,第一种叫读取结点,第二种叫写入结点。顾名思义,读取结点可以读取寄存器的数据,写入结点可以将数据写入寄存器。

为了进行庞大的数据交互,小衣一共使用了32个寄存器来交互数据,编号为0,1,2,,310,1,2,\dots,31。同时她准备了mm条指令用来测试她的CPU。她需要将这mm条指令按顺序塞入她的CPU。

为了体现她造的CPU的优雅,小衣设计的指令集非常特殊。每一个指令只有一个内容xx,表示这个指令需要使用第xx个寄存器。每一个指令将从CPU的开头,也就是第11个结点开始,一路运行到第nn个结点。由于小衣的CPU精通量子力学,对于任意一条到达第ii个结点的指令,它会花11个单位时间准备,然后在这个单位时间的末尾从第ii个结点自动跳到第i+1i+1个结点。当离开结点的瞬间,数据就会被读取或写入。同理,将这个指令放到第一个结点不需要花费时间,指令从第nn个结点离开需要花费11个单位时间。经过读取结点,CPU就会读取该寄存器的数据,而经过写入结点就会写入数据(至于写入数据从哪来的,小衣表示她的CPU会自动处理,不需要担心这些)。

小衣很快实现了一个优秀的流水线CPU,也就是说,她可以每隔一秒就塞入一个指令,让这些指令在CPU上同时跑。

然后小衣就遇到了data hazard[1]。具体来说,假如第ii和第jj条(i<ji<j)指令需要用到同一个寄存器,而且这个寄存器的值在执行第ii条指令后被写入了,那么对于CPU上的任何一个结点,它所需求(当然,无论是读取还是写入都算)的寄存器的值在执行第jj条指令的时候应该是被写入后的值。这在单循环的CPU里自然没有问题,但在流水线的CPU中,就有可能出现在第ii个指令对寄存器的写入还没发生之前,第jj条指令就已经被塞入CPU的情况。这种时候,CPU的数据就会发生错乱,而这自然是追求优雅的小衣深恶痛绝的。因此,为了避免data hazard的产生,对于这样满足条件的i,ji,j,小衣需要确保在第ii条指令的写入完成后再塞入第jj条指令。

同时,小衣还不满足于静态的CPU,因为她认为一成不变也是不优雅的。她还打算进行qq次修改。每一次修改会将某个结点的类型改变。现在小衣想知道,每一次修改后,她跑完所有测试指令需要花费的最短时间是多少。

输入格式

输入第一行包含三个整数n,m,qn,m,q

接下来一行包含nn个整数,每个整数表示对应的结点是读取结点还是写入结点,分别用0和1表示。

接下来一行包含mm个整数,每个整数表示对应的指令使用的寄存器。

接下来qq行,每行包含两个整数opt,idopt,id。若第一个整数是00,表示将某个结点修改成读取结点;若第一个整数是11,表示将某个结点修改成写入结点;idid表示修改结点的编号。

输出格式

输出包含q+1q+1行,每行仅包含一个整数,分别表示初始状态和每一次修改后需要花费的最短时间。

样例

3 3 3
0 1 0
0 1 0
0 2
1 2
1 3
5
5
5
6
10 14 9
1 0 0 0 1 1 1 0 1 0
7 6 2 1 5 7 5 6 1 6 7 3 7 1
0 2
1 9
0 9
0 4
1 7
1 8
1 8
0 8
1 6
44
44
44
38
38
38
41
41
38
38

对于第一个样例,初始状态下,直接每一秒放一个就能满足限制;第一次修改与第二次修改后,与初始状态的策略一致;第三次修改后,第三条指令需要等第一条指令离开CPU才能放入。

数据范围

数据点编号 nn mm qq 特殊性质
1 5\le5
2 10\le 10 20\le 20 10\le 10 仅使用前8个寄存器
3
4
5 105\le10^5 =0=0
6 105\le10^5 仅使用第1个寄存器
7
8 5000\le5000
9
10
11 105\le10^5
12
13
14
15

对于100%100\%的数据,1n105,1m105,0q1051\le n\le10^5,1\le m\le 10^5,0\le q\le 10^5

本题的每个测试点均为7分。


  1. 如果你了解的data hazard定义与这道题不同,请以这道题的定义为准。 ↩︎