← 返回题目列表

Codeforces · 1540/E

E. 美味佳肴

中文机器翻译题面 查看原题

请注意,内存限制不正常。

有$$$n$$$位厨师,编号为$$$1、2、\ldots、n$$$,必须为国王准备菜肴。厨师 $$$i$$$ 有技巧 $$$i$$$ 并且最初有一道美味的菜肴 $$$a_i$$$ 其中 $$$|a_i| \leq i$$$。每个厨师都有一份其他厨师的名单,他可以从中复制。为了防止厨师养成坏习惯,国王确保厨师 $$$i$$$ 只能模仿技艺更高超的厨师。

厨师们可以在一系列的日子里制作他们的菜肴。每天,厨师可以在两个阶段改变菜肴的口味。

1. 每天开始时,每个厨师都可以选择工作(或不工作)自己的菜肴,从而使自己的菜肴的美味程度倍增($$$a_i := i \cdot a_i$$$)(或什么都不做)。
2. 在所有厨师(想要的)完成自己的菜肴后,每个人开始观察其他厨师。特别地,对于厨师$$$i$$$名单上的每个厨师$$$j$$$,厨师$$$i$$$可以选择复制(或不复制)$$$j$$$的菜肴,从而将$$$j$$$的菜肴的美味添加到$$$i$$$的菜肴中($$$a_i := a_i + a_j$$$)(或什么都不做)。可以假设所有复制同时发生。也就是说,如果厨师$$$i$$$选择从厨师$$$j$$$复制,他将在阶段$$$1$$$结束时复制厨师$$$j$$$的菜肴的美味。

所有厨师都致力于最大限度地提高自己菜肴的美味,以取悦国王。

最后,您将收到 $$$q$$$ 查询。每个查询都是两种类型之一。

1. $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ — 求第 $$$k$$$ 天后的美味度 $$$a_l, a_{l+1}, \ldots, a_{r}$$$ 的总和。由于该值可能很大,因此请对 $$$10^9 + 7$$$ 求模。
2. $$$2$$$ $$$i$$$ $$$x$$$ - 国王在第 $$$1$$$ 天开始之前为第 $$$i$$$ 厨师的菜肴添加 $$$x$$$ 美味 ($$$a_i := a_i + x$$$)。请注意,因为国王想要看到更美味的菜肴,所以他只添加正的美味($$$x > 0$$$)。

请注意,$$$1$$$ 类型的查询独立于所有其他查询。具体来说,$$$1$$$类型的每个查询都是一个场景,并且不会改变任何菜肴的初始味道$$$a_i$$$以供将来查询。请注意,$$$2$$$ 类型的查询是累积的,只会改变菜肴的初始味道 $$$a_i$$$。有关查询示例,请参阅注释。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 300$$$) — 厨师的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-i \le a_i \le i$$$)。

接下来的 $$$n$$$ 行每行以整数 $$$c_i$$$ ($$$0 \le c_i < n$$$) 开头,表示第 $$$i$$$ 厨师可以复制的厨师数量。该数字后跟 $$$c_i$$$ 不同的整数 $$$d$$$ ($$$i < d \le n$$$),表示允许厨师 $$$i$$$ 在每天的 $$$2$$$ 阶段从厨师 $$$d$$$ 复制。

下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。

接下来的 $$$q$$$ 行中的每一行都包含以下两种类型之一的查询:

- $$$1$$$ $$$k$$$ $$$l$$$ $$$r$$$ ($$$1 \le l \le r \le n$$$; $$$1 \le k \le 1000$$$);
- $$$2$$$ $$$i$$$ $$$x$$$ ($$$1 \le i \le n$$$; $$$1 \le x \le 1000$$$)。

保证至少有一个第一类型的查询。

输出

对于第一种类型的每个查询,打印一个整数 - 查询的答案。

示例

输入 #1

5
1 0 -2 -2 4
4 2 3 4 5
1 3
1 4
1 5
0
7
1 1 1 5
2 4 3
1 1 1 5
2 3 2
1 2 2 4
2 5 1
1 981 4 5

输出 #1

57
71
316
278497818

注意

以下是允许每个厨师复制的厨师集:

- $$$1$$$: $$$\{2, 3, 4, 5\}$$$
- $$$2$$$: $$$\{3\}$$$
- $$$3$$$: $$$\{4\}$$$
- $$$4$$$: $$$\{5\}$$$
- $$$5$$$: $$$\emptyset$$$ (没有其他厨师)

以下是示例的描述。

对于 $$$1$$$ 类型的第一个查询,初始美味值为 $$$[1, 0, -2, -2, 4]$$$。

第一天最终成绩如下图:

1. $$$[1, 0, -2, -2, 20]$$$(厨师$$$5$$$ 做他的菜)。
2. $$$[21, 0, -2, 18, 20]$$$(厨师 $$$1$$$ 和厨师 $$$4$$$ 复制自厨师 $$$5$$$)。

因此,$$$1$$$-st 查询的答案是 $$$21 + 0 - 2 + 18 + 20 = 57$$$。

对于第 $$$5$$$ 查询($$$3$$$-rd 类型为 $$$1$$$)。初始美味值现在为 $$$[1, 0, 0, 1, 4]$$$。

第一天

1. $$$[1, 0, 0, 4, 20]$$$(厨师$$$4$$$ 和$$$5$$$ 正在制作他们的菜肴)。
2. $$$[25,0, 4, 24, 20]$$$(厨师$$$1$$$从厨师$$$4$$$和$$$5$$$复制,厨师$$$3$$$从厨师$$$4$$$复制,厨师$$$4$$$从厨师$$$5$$$复制)。

第 2 天

1. $$$[25, 0, 12, 96, 100]$$$(除了厨师 $$$2$$$ 之外的所有厨师都在制作他们的菜肴)。
2. $$$[233, 12, 108, 196, 100]$$$(厨师 $$$1$$$ 复制自厨师 $$$3$$$、$$$4$$$ 和 $$$5$$$,厨师 $$$2$$$ 从 $$$3$$$,厨师 $$$3$$$ 从 $$$4$$$,厨师$$$4$$$ 来自厨师 $$$5$$$)。因此,第 $$$5$$$ 查询的答案是 $$$12+108+196=316$$$。

可以证明,在我们描述的每个步骤中,所有厨师都以最佳方式移动。