#PQJ1976x10365. QOJ 1976_10365

    ID: 2770 传统题 1500ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:BJOI 2017线段树分块

QOJ 1976_10365

题目背景

拿到了飞机的驾照(?),这样补给就不愁了 XXXX年XX月XX日

拿到了喷气机(??)的驾照,这样就飞得更快了 XXXX年XX月XX日

拿到了攻击机(???)的驾照(不存在的) XXXX年XX月XX日

用铅版做夹层的话,机身可是会变重的呢 XXXX年XX月XX日

幸酱的特制快递,精确投递到了目标地点

又是核平的一天。

天音正在给喷气机做保养,并充填燃料。 这种喷气机是某姬(?????)特别制作的,发动机拥有三种工作状态:

通常型(Original):在高空平飞或隐蔽飞行时进行的低功耗高效率工作状态 后期型(Extended):为在俯冲时最大化能量利用率而特别改造过的工作状态 增强型(Enhanced):在俯冲攻击结束后为产生极限扭力抬高高度的工作状态

在一次攻击中,喷气机将会经历 "通常 → 后期 → 增强 → 通常" 的工作流程。

不同工作状态中,燃料的利用效率是不同的。 现在天音正在调整喷气机燃料装填序列,你需要做的就是:

求出燃料能产生的最大总能量。

为什么是你? 和平还是核平,选一个吧。

题目描述

初始燃料序列为空。每次操作会向序列中的第 𝑝 𝑖 个位置添加 𝑥 𝑖 单位的同种燃料。

该燃料每单位在三种工作状态下能产生的能量分别为 𝑎 𝑖 ,   𝑏 𝑖 ,   𝑐 𝑖 。

添加的位置 𝑝 𝑖 是指,在添加后,加入的第一个单位燃料前面有 𝑝 𝑖 个单位的原燃料。 全部的 𝑥 𝑖 单位燃料依次放置,然后原来在 𝑝 𝑖 位置的燃料(如果有的话)依次向后排列。

对于一个确定的燃料序列,其能产生的最大总能量为:

将序列依次分成 "通常 → 后期 → 增强 → 通常" 四段(每段可以为空),每一段在对应工作状态下产生的能量之和的最大值。

对于每次添加操作,你需要给出该次操作使得最大总能量增加了多少。

如果对这种计算方式没有直观的感受,可以查看样例说明。

输入格式

第一行一个整数 𝑛 ,表示操作个数。

接下来 𝑛 行,每行包含 5 个整数 𝑝 𝑖 ,   𝑎 𝑖 ,   𝑏 𝑖 ,   𝑐 𝑖 ,   𝑥 𝑖 ,空格分隔,含义如下:

𝑝 𝑖 :插入的位置 𝑎 𝑖 ,   𝑏 𝑖 ,   𝑐 𝑖 :单位燃料在通常、后期、增强三种状态下产生的能量 𝑥 𝑖 :添加的燃料数量 输出格式

输出 𝑛 行,每行一个整数,表示该次操作后燃料序列所能产生的最大总能量增加了多少。

样例数据 样例输入 5 0 25 37 46 2 1 32 14 16 3 3 99 77 88 4 2 43 68 57 5 14 72 36 18 6 样例输出 92 75 396 319 432 样例解释

第一次操作后,燃料序列为 [1 1] 最大能量发生方式为 [En1 En1],共 46 + 46

92

第二次操作后,燃料序列为 [1 2 2 2 1] 最大能量发生方式为 [Or1 Or2 Or2 Or2 En1],共 25 + 32 + 32 + 32 + 46

167 ,增加了 167 − 92

75

第三次操作后,燃料序列为 [1 2 2 3 3 3 3 2 1] 最大能量发生方式为 [Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1],增加了 99 × 4

396

第四次操作后,燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 2 1] 最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]

第五次操作后,燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 2 1 5 5 5 5 5 5] 最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]

子任务

对于 20 % 的数据, 𝑛 ≤ 1 000 。

对于 50 % 的数据, 𝑛 ≤ 10 4 。

对于 100 的数据: 1 ≤ 𝑛 ≤ 10 5 , 1 ≤ 𝑎 𝑖 ,   𝑏 𝑖 ,   𝑐 𝑖 ≤ 10 4 , 1 ≤ 𝑥 𝑖 ≤ 10 9 。后 50 % 的数据存在一定的梯度。

保证插入时序列中至少已有 𝑝 𝑖 单位的燃料