#P7324. [2018年12月西安集训]核糖

    ID: 7338 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300数据结构分块凸包模拟构造字符串

[2018年12月西安集训]核糖

题目描述

有 nn 颗核糖排成一列,第 ii 颗的美味度为 viv_i,可以为负数。

  • 加工:选定区间 [L,R][L,R],将其中每颗核糖的美味度都加上 kk。kk 可以为负数。
  • 询问:给定区间 [L,R][L,R],在其中选一个位置 xx,取出从第 11 颗到第 xx 颗的核糖作为礼物。求礼物美味度之和的最大值。

输入格式

第一行一个整数 nn。第二行 nn 个整数 v1,…,vnv_1,\ldots,v_n。第三行一个整数 mm,表示操作数。

接下来 mm 行,每行是以下一种操作:

  • 0 L R k:将 [L,R][L,R] 中的每个 viv_i 增加 kk。
  • 1 L R:求 max⁡L≤x≤R∑i=1xvi\max_{L\le x\le R}\sum_{i=1}^x v_i。

输出格式

每次询问输出一行一个整数。保证答案在 64 位有符号整数范围内。

样例

5
1 8 -3 3 -7
3
1 1 5
0 1 3 6
1 2 4
9
22

数据范围

样例中第二次询问时,选择 x=4x=4,礼物的美味度为 7+14−2+3=227+14-2+3=22。

  • 对于 10%10\% 的数据,n,m≤3000n,m\le3000。
  • 对于另外 15%15\% 的数据,所有修改操作满足 L=RL=R。
  • 对于另外 15%15\% 的数据,所有询问操作满足 L=RL=R。
  • 对于另外 20%20\% 的数据,修改操作不超过 10001000 个,所有询问满足 L∈[1,100]L\in[1,100]、R∈[n−100,n]R\in[n-100,n]。
  • 原 PDF 对全部数据给出的上限是 n,m≤100000n,m\le100000。本评测站原有补充说明为 N,M≤500000N,M\le500000,以及 g,r≤400000000g,r\le400000000(原说明未定义 g,rg,r)。

原 PDF 题面