【泉七培训-杨国烨】出纳员zgg

2014年12月26日1,1590

【题目描述】

zgg去当出纳员了!zgg所在的公司的工资是按年发放的。在每年的元旦,每个员工的工资额会被修改为0元;在每年的除夕,员工按工资额领取相应的工资。zgg的上司是一位和蔼可亲的老爷爷,他经常给员工们提升工资。而zgg的工作,就是帮助所有员工统计最后的工资额。

老爷爷只会用以下两种指令给员工们提升工资:1.让某个员工的工资额提升X元;2.让所有员工的工资额变成原来的X倍。

然则,由于老爷爷实在是太和蔼了,以至于提升工资的指令数目达到了10^10级别,这无疑使zgg的工作变得困难重重。

还好,老爷爷的指令最多只有N种。为了提高工作效率,zgg又定义了一些宏指令:某个宏指令包括2个分指令(可以是宏指令或基本指令),执行宏指令相当于先后执行这两个分指令。

许多年后,zgg发现,这些指令构成了一棵二叉树:如果把宏指令当成某个结点,那么两个分指令则相当于该结点的左右儿子,而叶子结点就是那些基本指令。

现在,除夕即将来临,zgg却发现自己的工作一点都没

有完成!还好,所有的指令都按顺序记录下来了。为了自己的工资,zgg想请你帮忙,统计出所有人的工资。

【输入格式】

第一行三个正整数N,M,Q,分别表示基本指令的种类数目、所有指令的数目、员工数目。

接下来N行,第i+1行代表第i种指令(基本指令),有两种类型:

1.每行3个整数1 X Y:表示让X号员工的工资额提升Y元;

2.每行2个整数2 X:表示让所有员工的工资额变为原来的X倍。

接下来N-1行,第i+N+1行代表第i+N种指令(宏指令),每行2个正整数A B,表示第i+N种指令的分指令。

接下来M行,每行一个正整数A,表示执行A指令。

【输出格式】

共Q行,每行一个整数Ansi,表示第i号员工最后的工资。

【样例输入】

4 5 2

1 2 3

1 1 1

2 2

1 1 10

6 7

2 1

3 4

2

6

7

5

3

【样例输出】

80

36

【数据规模和约定】

有50%的数据平均分布在测试点中,满足:基本指令均为第1种指令。

30%的数据满足N<=200,M<=200,Q<=100;

60%的数据满足N<=10000,M<=20000,Q<=100;

100%的数据满足N,M,Q<=100000,所有员工任何时候的工资额都不会超过10^9元。

第一种指令1 X Y满足1<=X<=Q,0<=Y<=100;

第二种指令2 X满足0<=X<=10。

题解。。。

因为所有员工任何时候工资不超过10^9,所以有效的乘法操作不超过31个,*1视为+0

那么依次处理宏指令,若这个宏指令的子树中无乘法运算则打标记,若有乘法运算暴力处理整棵树的标记再暴力执行这个宏指令

但是注意到有*0的操作

所以应该从最后一个有子树中有*0的宏指令开始做,前面的无视,这样才能保证复杂度

但是还有一个问题,所有其余的乘法操作并不一定都有效!可能序列全为0时,执行一堆乘法。。。

还要记录下每个宏指令是否有有效的加法操作,序列都为0的时候无视乘法

最后似乎还有一种情况,最后一个有子树中有*0的宏指令执行之后,不好确定序列是否全0,嗯暴力判断一下