你问我为什么只有 A,B，因为我这可悲的实力只能让我做出 A,B。

由于我是个 Rating 300 不到的萌新，所以没有资格玩 Rated ARC。而且我太菜了，A 题做了一个小时后面的题也没时间做。

如果你觉得我写的好，就点赞评论吧。

A – Always Increasing

题目传送门。

题目描述

有一个长度为 $N$ 的正整数序列 ${A_N}$，有 $Q$ 种操作，第 $q$ 种操作给定 $i_q$ 和 $x_q$，将 $A_{i_q}\gets A_{i_q} + x_q$。

要求任意时刻，序列 $A$ 呈单调递增。请给出最小的 $\sum A$，满足要求。

思路

观察到操作的顺序是会影响结果的。

维护两个数组：$B$ 和 $C$。

若 $i_q\ge 2$，则其会对位于 $i_q-1$ 的操作产生影响，即在 $i_q-1$ 上的 $A$ 的值只要加上其加上的值减去 $x_q$ 即可。因为要满足 $A_{i_q} > A_{i_q-1}$，而当 $A_{i_q} \gets A_{i_q} + x_q$，要前者小于 $A_{i_q}+x_q$，若 $A_{i_{q}-1}$ 略大，会影响后面所有的值（因为题目要求单调递增）。所以想到此构造方法。

如果有多次操作，自然在 $A$ 的构造上选择其中最大的即可满足所有操作。$C_i$ 表示最大的修改值。

若 $i_q=n$，其不产生影响，忽略。

提交记录。

B – Remove Median Operation

题目传送门。

题目大意

有序列 ${A_N}$ 和序列 ${B_M}$，满足其均为正整数，以及 $n$ 是偶数。

有 $Q$ 次修改，每次修改有两种类型，且给定 $i_q$ 和 $x_q$：
– 类型 $1$，$A_{i_q}\gets x_q$。
– 类型 $2$，$B_{i_q} \gets x_q$。

每次修改后给出以下答案：

（这些操作不影响序列值）将 $B_j(j=1,2,3,\ldots,M)$ 依次加入序列 $A$ 中，每次加入后删去中位数，求剩下的序列的和。

思路

个人感觉 A 比 B 思路难，B 比 A 实现难。

手玩几个样例能发现性质——将 $A$ 和 $B$ 按照值桶排序，每个值上记录该值的数目。则从第一个前面值的和大于等于 $\frac{n}{2}$ 的位置开始，到中间的第一个和大于等于 $m$ 的位置结束，这段的值是要删去的，剩下的就是答案。

手玩一下样例 $1$ 的第一组询问：

此时 $A=(5,1,3,3)$，$B=(1,2)$。将其值映射到另一个数组上，值为其下标在两数组中出现的位置，有 $C=(2,1,2,0,1)$。

前面和为 $\frac{n}{2}$ 的位置截止到 $1$，中间和为 $m$ 的位置截止到 $3$（因为 $\sum_{i=3}^2 C_i=3$。多删了 $1$ 个。

因此要删的值是 $1\times 2+1\times 3$，此时和是 $15$。故答案是 $10$。

修改用线段树或者树状数组维护，查询最早位置用二分。而映射到值域的操作中，值域太宽泛了，空间直接爆掉，所以将所有的 $A_i$、$B_i$、修改操作先存下来，直接离散化再离线化。回头处理这些查询。

也许是这道题放的比较松，或者 AtCoder 的评测机太给力了，直接答案二分套上原生的线段树区间查询加持线段树逆天常数它还是过了。

为什么这是正确的

让我们来感性地理解一下这个过程。

一个 $B_j$ 加入后，有三种情况：
– 其大于中位数，中位数右移。
– 其小于中位数，中位数左移。
– 其就是中位数，中位数不动。

using namespace std;

所以中位数从一个位置开始，一直左移右移或不动，在序列中的位置变化是连续的。

而其选择的一直是中间的值，所以在刚刚的序列中，也是选择中间 $m$ 个值的和删去。

提交记录。