CF1540E Tasty Dishes

注意，本题的内存限制不同于常规题目。 有 $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$ 的菜肴美味度加到自己的菜肴上（$a_i := a_i + a_j$），也可以选择不模仿。可以认为所有的模仿操作是同时进行的。也就是说，如果厨师 $i$ 选择模仿厨师 $j$，他会复制第 $1$ 阶段结束后厨师 $j$ 的菜肴美味度。 所有厨师都希望最大化自己菜肴的美味度，以取悦国王。 最后，你会得到 $q$ 个询问。每个询问有两种类型： 1. $1\ k\ l\ r$ —— 询问第 $k$ 天结束后，第 $l$ 位到第 $r$ 位厨师的美味度之和。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。 2. $2\ i\ x$ —— 在第 $1$ 天开始前，国王给第 $i$ 位厨师的菜肴增加 $x$ 的美味度（$a_i := a_i + x$）。注意，国王只会增加正数的美味度（$x > 0$）。 注意，类型 $1$ 的询问彼此独立。具体来说，每个类型 $1$ 的询问都是一个独立的场景，不会影响其他询问中任何菜肴的初始美味度。类型 $2$ 的询问是累加的，只会改变菜肴的初始美味度。详见样例说明。

第一行包含一个整数 $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 \times 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$ 的询问。

对于每个类型 $1$ 的询问，输出一个整数，表示该询问的答案。

以下是每位厨师可以模仿的厨师集合： - $1$：$\{2, 3, 4, 5\}$ - $2$：$\{3\}$ - $3$：$\{4\}$ - $4$：$\{5\}$ - $5$：$\emptyset$（没有可模仿的厨师） 以下是样例的说明。 对于第一个类型 $1$ 的询问，初始美味度为 $[1, 0, -2, -2, 4]$。 第 1 天结束后的结果如下： 1. $[1, 0, -2, -2, 20]$（第 5 位厨师加工了自己的菜肴）。 2. $[21, 0, -2, 18, 20]$（第 1 位和第 4 位厨师模仿了第 5 位厨师）。 因此，第 1 个询问的答案为 $21 + 0 - 2 + 18 + 20 = 57$。 对于第 5 个询问（第 3 个类型 $1$ 的询问），初始美味度为 $[1, 0, 0, 1, 4]$。 第 1 天： 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$。 可以证明，在我们描述的每一步中，所有厨师都采取了最优策略。 由 ChatGPT 4.1 翻译