P4807 [CCC 2017] 地铁交通

**滥用本题评测将被封号**

**译自 [CCC2017](https://cemc.math.uwaterloo.ca/contests/computing/2017/index.html) Senior T5「[RMT](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%201/seniorEF.pdf)」** RMT 地铁交通运行着一个不寻常的地铁系统。有 $N$ 个地铁站，从 $1$ 到 $N$ 编号。有 $M$ 条地铁线路，从 $1$ 到 $M$ 编号，每个地铁站只属于一条线路且每条线路至少经过一个地铁站。整个地铁网络呈圆形。也就是说，如果有一个编号为 $S$ 的地铁站，那么与它同一线路的下一个地铁站是下一个编号比它大的地铁站。除非 $S$ 是同线路中编号最大的地铁站，在这种情况下，它的下一个地铁站是同一线路中编号最小的地铁站。 RMT 正在以志愿者对他们的系统进行负载测试。测试从每一站以一列地铁列车开始，且对于每一个 $i$，会有 $A_i$ 个志愿者在第 $i$ 站的测试列车上。在整个测试期间，志愿者不会离开对应的列车。 测试过程中，RMT 会进行 $Q$ 个操作，每个操作只有两种可能：一种是询问第 $l$ 站到第 $r$ 站地铁上的志愿者人数；或是在线路 $x$ 运行所有的地铁。当有一列地铁在 $x$ 线路运行，它会前往线路中的下一站。 你是 RMT 的铁杆骨灰级粉丝，所以你自愿协助他们进行操作并告诉他们操作的结果。

第一行，三个整数，$N,M$ 和 $Q(1 \le M \le N \le 150\ 000;1 \le Q \le 150\ 000)$。 第二行，$N$ 个整数 $L_1,L_2,\dots,L_N$，表示每个地铁站所属线路的编号。 第三行，$N$ 个整数 $A_1,A_2,\dots,A_N$，表示每个地铁站起始时刻的志愿者人数。 以下 $Q$ 行，每行只有以下其中一种形态： - `1 l r`，表示一个询问 $(1 \le l \le r \le N)$。 - `2 x`，表示 RMT 会在 $x$ 线路运行 $(1 \le x \le M)$。

对于每个询问，输出一行，表示询问的答案。

### 样例解释 1 地铁系统如下图所示，地铁站编号为 $1$ 到 $5$，由编号为 $1$ 或 $2$ 的线路连接：  开始时，每个地铁站的志愿者人数为 $\{1,2,3,4,5\}$。 第一个询问的答案为 $1+2+3+4+5=15$。 线路 $1$ 被运行之后，每个地铁站的志愿者人数为 $\{3,2,1,4,5\}$。 第二个询问的答案为 $1+4+5=10$。 线路 $2$ 被运行之后，每个地铁站的志愿者人数为 $\{3,5,1,2,4\}$。 第三个询问的答案为 $3+5+1=9$。 #### 样例解释 2 地铁系统如下图所示，地铁站编号为 $1$ 到 $3$，只有线路 $1$ 连接：  第一次询问之前，每个地铁站的志愿者人数为 $\{114,101,109\}$。 第二次询问之前，每个地铁站的志愿者人数为 $\{109,114,101\}$。 第三次询问之前，每个地铁站的志愿者人数为 $\{101,109,114\}$。 第四次询问之前，每个地铁站的志愿者人数为 $\{114,101,109\}$。 对于 $\frac2{15}$ 的数据，$N \le 1\ 000,Q \le 1\ 000$。 对于另外 $\frac2{15}$ 的数据，$L_i \le L{i+1}(1 \le i < N)$。 对于另外 $\frac3{15}$ 的数据，$M \le 200$。 对于另外 $\frac3{15}$ 的数据，每条线路的地铁数量都不超过 $200$。