#B. [CZOJ 一周一测 R1 B] 视界巡航

    传统题 1500ms 256MiB

[CZOJ 一周一测 R1 B] 视界巡航

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

视界不现,巡航欲见。

题目背景

小时候,每天晚上邹锦舒的妈妈都会用望远镜给邹锦舒看一闪一闪的月亮。可现在,因为城市污染太严重了,邹锦舒看不见月亮。多怀念小时候的时光啊......

有一天,邹锦舒睡觉的时候,又梦见了小时候那美丽的月亮一闪一闪,周围有群星点缀,好漂亮......

可好景不长,邹锦舒被他的妈妈叫醒去上学了。

题目描述

邹锦舒很不舍,于是开始模拟起月亮的闪烁值。

月亮的初始闪烁值为 xx,周围一共有 nn 颗星星,第 ii 颗星星的闪烁值为 yiy_i。每一颗星星都会和月亮形成一个整体。换句话说,第 ii 个整体的闪烁值为 x+yix+y_i。现在有三种可能:

  1. 月亮的闪烁值变为 aa
  2. 把有着最大闪烁值的星星的闪烁值变成 bb
  3. 把有着最小闪烁值的星星的闪烁值变成 cc

请帮邹锦舒算出,每一次操作后,最大的整体闪烁值是多少。

输入格式

第一行两个整数 nnxx,表示星星的总数和月亮的闪烁值。

第二行 nn 个整数,表示每一个星星的闪烁值。

第三行一个整数 tt,表示操作的总数。

接下来 tt 行,首先一个整数 opop,表示操作的类型(即为上文的 112233)。

然后是一个整数 aabbcc,具体描述见上。

输出格式

tt 行,每行一个整数,表示一颗星星和月亮的总和的最大值。

3 5
1 2 3
3
2 1
1 3
3 10
7
5
13

提示

认为时间复杂度正确但只有暴力分的请使用更快的输入输出方式

现在有 33 颗星星,闪烁值分别为 {1,2,3}\{1,2,3\}

第一次,将有着最大闪烁值的星星,也就是第三颗星星的闪烁值改为 11,也就是变成了 {1,2,1}\{1,2,1\}。此时,最大的闪烁值应为第二颗星星加上月亮,也就是 2+5=72+5=7

第二次,将月亮的闪烁值更改为 33,此时星星的所有闪烁值是 {1,2,1}\{1,2,1\} 最大的闪烁值为 2+3=52+3=5

第三次,将有着最小闪烁值的星星,也就是第一颗星星的闪烁值改成 1010,也就是变成了 {10,2,1}\{10,2,1\}。此时,最大的闪烁值应为第二颗星星加上月亮,也就是 10+3=1310+3=13如果有多个相同的最大/最小,我们只更改其中的第一个。

测试点编号 nn tt x,a,b,cx,a,b,c 特殊性质
121\sim 2 100\leq 100 1000\leq 1000
363\sim 6 2×105\leq 2\times 10^5 109\leq 10^9 A\tt{A}
787\sim 8 100\leq 100 1000\leq 1000
9129\sim 12 2×105\leq 2\times 10^5 109\leq 10^9 B\tt{B}
131413\sim 14 100\leq 100 1000\leq 1000
151815\sim 18 2×105\leq 2\times 10^5 109\leq 10^9 C\tt{C}
192019\sim 20

特殊性质 A\tt{A}:保证只有 11 操作。

特殊性质 B\tt{B}:保证只有 22 操作。

特殊性质 C\tt{C}:保证只有 33 操作。

你可能需要一些更加快速的读入方式。

[CZR-001] CZOJ Weekly Exercise Round 1

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-7-7 17:00
结束于
2023-7-7 22:30
持续时间
5.5 小时
主持人
参赛人数
54