[CTFPC-2] Lanterns

ID: 190

传统题

1000ms

128MiB

难度: 8

上传者:

标签>

CTFPC

题目描述

2se 给了你一道有趣的数据结构题——

维护两个序列 $\{a_n\},\{b_m\}$ （ $m \to +\infty$ ），支持以下操作 $q$ 次：

格式	描述
`add i v`	$b_i \gets v$
`update l r v`	$a_i \gets a_i+v\ (l \le i \le r)$
`inq i`	在 $\{a_n\}$ 末尾插入 $b_i$ （保证 $b_i \ne -1$ ），然后 $b_i \gets -1$
`mninq`	令 $b_i$ 为 $\{b_n\}$ 中的最小非负值（保证存在且唯一），在 $\{a_n\}$ 末尾插入 $b_i$ ，然后 $b_i \gets -1$
`mxinq`	令 $b_i$ 为 $\{b_n\}$ 中的最大值（保证存在且唯一），在 $\{a_n\}$ 末尾插入 $b_i$ ，然后 $b_i \gets -1$
`ask l r`	输出 $a_l + a_{l+1} + \ldots + a_r$ 的值

其中 $\{a_n\}$ 的初值给定， $b_i$ 初始时均为 $-1$ 。

第一行两个正整数 $n,q$ 。

第二行 $n$ 个正整数 $a_1 \sim a_n$ 。

下面 $q$ 行，每行一个操作。

对每个 ask 操作输出答案。

1 16
5000
ask 1 1
add 2 400
add 4 300
add 6 200
add 8 100
inq 2
ask 1 2
mninq
ask 1 3
mxinq
ask 1 4
update 2 3 10000
ask 1 4
ask 2 4
ask 3 4
ask 4 4