AT_past201912_h まとめ売り

维护一个长为 $n$ 的数列 $c$。有以下三种操作： - `1 x a`：若 $c_x \ge a$，则将 $c_x$ 的值减去 $a$；否则，忽略此操作。 - `2 a`：对于所有满足 $x$ 为奇数且 $1 \le x \le n$ 的整数 $x$，若每一个 $x$ 均满足 $c_x \ge a$，则将每一个 $c_x$ 的值都减去 $a$；否则，忽略此操作。 - `3 a`：对于所有满足 $1 \le x \le n$ 的整数 $x$，若每一个 $x$ 均满足 $c_x \ge a$，则将每一个 $c_x$ 的值都减去 $a$；否则，忽略此操作。 一共进行了 $q$ 次操作。请在所有操作完成后，输出全部操作中减去的数之和。

第一行输入数列长度 $n$。 第二行输入 $n$ 个整数，表示数列 $c$。 第三行输入操作次数 $q$。 最后 $q$ 行，每行一个操作，格式见题。

在所有操作完成后，输出全部减去的数值之和。 ### 数据规模与约定 $1 \le n,q \le 200000$，$1 \le c_i,a \le 10^9$，$1 \le x \le n$，输入数值均为整数。

### 注意 この問題に対する言及は、2019年12月29日 05:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 1\ \leqq\ N\ \leqq\ 200,000 $ - $ 1\ \leqq\ C_i\ \leqq\ 10^9 $ - $ 1\ \leqq\ Q\ \leqq\ 200,000 $ - $ S_i $ は以下のいずれかの形式の文字列である。 - `1 x a` ($ 1\ \leqq\ x\ \leqq\ N $ かつ $ 1\ \leqq\ a\ \leqq\ 10^9 $) - `2 a` ($ 1\ \leqq\ a\ \leqq\ 10^9 $) - `3 a` ($ 1\ \leqq\ a\ \leqq\ 10^9 $) - 入力で与えられる数は全て整数である。 ### Sample Explanation 1 最初、各カードの在庫数はそれぞれ $ 5,3,3,5 $ である。 各クエリは以下のように処理される。 1. カード $ 2 $ を $ 1 $ 枚販売する。このクエリの後、在庫数は $ 5,2,3,5 $ となる。 2. カード $ 1,3 $ を $ 2 $ 枚ずつ販売する。このクエリの後、在庫数は $ 3,2,1,5 $ となる。 3. カード $ 3 $ の在庫が足りないため、何もしない。 4. 在庫が足りないため、何もしない。 5. 全種類のカードを $ 1 $ 枚ずつ販売する。このクエリの後、在庫数は $ 2,1,0,4 $ となる。 6. 在庫が足りないため、何もしない。 このように、$ 1,2,5 $ 番目のクエリで $ 1,4,4 $ 枚のカードを販売し、合計販売枚数は $ 9 $ 枚となる。