原始人,启动 / 【模板】线段树

原始人,启动 / 【模板】线段树

题目背景

你说的对,但是《 原神 》是由 米哈游自主研发 的一款全新开放世界冒险游戏。游戏发生在一个被称作「 提瓦特 」的幻想世界,在这里,被神选中的人将被授予「 神之眼 」,导引元素之力。你将扮演一位名为「 旅行者 」的神秘角色在自由的旅行中邂逅性格各异、能力独特的同伴们,和他们一起击败强敌,找回失散的亲人——同时,逐步发掘「 原神 」的真相。

因为你的 素养很差,我现在每天玩原神都能赚 150 原石,每个月差不多 5000 原石的收入, 也就是现实生活中每个月 5000 美元 的收入水平,换算过来最少也 30000人民币,虽然我 只有 14岁,但是已经超越了 中国绝大多数人(包括你)的水平,这便是 原神 给我的骄傲的 资 本

毫不夸张地说,《 原神 》是 miHoYo 迄今为止规模最为宏大,也是最具野心的一部作品。即便在经历了 8700 个小时的 艰苦战斗 后,游戏还有许多尚未发现的秘密,错过的武器与装备,以及从未使用过的法术和技能。

尽管游戏中的战斗体验和我们之前在烧机系列游戏所见到的没有多大差别,但游戏中各类 精心设计 的敌人以及Boss战已然将战斗抬高到了一个全新的水平。就和几年前的《 塞尔达传说 》一样,《 原神 》也是一款能够推动同类游戏向前发展的优秀作品。

题目描述

在 \(\text{OP}\) 的一生中有许多的 资本
你知道 \(\text{OP}\) 的一生只有 \(n\) 秒,而现在告诉你,假如把 \(\text{OP}\) 的一生看做一个 \([1,n]\) 的区间,它会花费 \([L_i,R_i]\) 来在每秒钟获得 \(x\) 原石。而且,\(\text{OP}\) 都是《 时间管理大师 》(那是原神给他们的资本),他们不仅可以宏观调控自己的时间,而且其可以多次花费同一区间。

输入格式

第一行两个正整数 \(n,m\),分别表示 \(\text{OP}\) 的生命长度和 \(\text{OP}\) 浪费它生命的次数。

第二行包含 \(n\) 个用空格分隔的整数,其中第 \(i\) 个数字表示数列第 \(i\) 项的初始值。

接下来 \(m\) 行,表示对应的操作。

  1. 1 L R x 表示在 \([L,R]\) 区间内 \(\text{OP}\) 浪费它的生命来在每秒钟获得 \(x\) 原石。
  2. 2 L R 表示查询目前已知的安排下在 \([L,R]\) 区间内 \(\text{OP}\) 所获得的 美元数人民币数

输出格式

输出若干行,每行2个整数,即所有操作2的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

样例输出 #1

11 66
8 48
20 120

提示

对于 \(30\%\) 的数据: \(n \le 8,m \le 10\)。

对于 \(70\%\) 的数据: \(n \le 10^3,m \le 10^4\)

对于 \(100\%\) 的数据: \(1 \le n,m \le 10^5\)

保证任意时刻数列中所有元素的绝对值之和 \(\le 10^{18}\)

提示:题目描述有时候也很有用

【样例解释】

操作次数 输入内容 \(a_1\) \(a_2\) \(a_3\) \(a_4\) \(a_5\) 输出结果
0 \ 1 5 4 2 3 \
1 2 2 4 1 5 4 2 3 11 66
2 1 2 3 2 1 7 6 2 3 \
3 2 3 4 1 7 6 2 3 8 48
4 1 1 5 1 2 8 7 3 4 \
5 2 1 4 2 8 7 3 4 20 120

信息

ID
1047
难度
9
分类
线段树 点击显示
标签
递交数
9
已通过
3
通过率
33%
被复制
1
上传者

相关

在下列训练计划中:

模板 | Templates