C. 游戏

题目描述

小W是最近迷上了一款游戏。

在这个游戏里面，他一共拥有 $n$ 个角色，编号分别是 $1, 2, \dots, n$。在游戏里面角色一共有 $m+1$ 等级，分别是 $0, 1, 2, \dots, m$，等级是由经验值决定的。形式化的，游戏有 $m$ 个参数 $a_1, a_2, \dots, a_m$，满足 $a_1 < a_2 < a_3 < \dots < a_m$。若某个角色的经验值是 $x$，那么他的等级就是满足 $x \ge a_i$ 的最大的 $i$，（当 $x < a_1$ 时是 $0$）。

现在小W可以干两件事情：

1. 打怪：带上编号在某一个区间 $[l,r]$ 内所有角色去打怪，这样结束之后这些角色都可以得到 $x$ 的经验值
2. 氪金：充值之后把编号为 $p$ 的角色的经验值魔改为 $x$。

小W不时的想要估算自己的战斗力，他会给出一些询问，每个询问给出 $[l,r]$，他想要知道编号在 $[l,r]$ 区间内的所有角色的等级的和。

输入格式

第一行三个整数 $n$，$m$，$q$。

第二行 $m$ 个整数，表示 $a_1, a_2, \dots, a_m$。

第三行 $n$ 个整数，表示每个角色初始的经验值。

接下来 $q$ 行，每行第一个数表示 $type$：

• $type = 1$：打怪，后面接 $3$ 个整数，表示 $l, r, x$。
• $type = 2$：氪金，后面接 $2$ 个整数，表示 $p, x$。
• $type = 3$：后面接 $2$ 个整数 $l, r$，表示一组询问。

输出格式

输出一些行，每行一个整数，表示第 $i$ 个询问的答案。

样例1

input

5 5 10
2 4 6 8 10
1 1 1 1 1
3 1 5
1 1 5 1
3 1 5
1 1 4 1
1 2 5 1
3 2 4
3 1 5
2 3 100
3 1 5
3 3 3

output

0
5
6
8
11
5

限制与约定

对于 $30\%$ 的数据，$n, q \le 1000$。

对于另外 $5\%$ 的数据，不存在 $type = 1$ 和 $type = 2$。

对于另外 $10\%$ 的数据，不存在 $type = 1$。

对于另外 $15\%$ 的数据，不存在 $type = 2$。

对于 $100\%$ 的数据，$n, q \le 10^5, m \le 10$。

时间限制：1s

空间限制：512MB

下载

样例数据下载