UOJ Logo

NOI.AC

#38. 游戏

统计

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

下载

样例数据下载