题解：AT_arc210_b [ARC210B] Remove Median Operations

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

加入后，有三种情况：

其大于中位数，中位数右移。
其小于中位数，中位数左移。
其就是中位数，中位数不动。

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

而其选择的一直是中间的值，所以在刚刚的序列中，也是选择中间

m

个值的和删去。

提交记录。

题解：AT_arc210_b [ARC210B] Remove Median Operations

文章操作

B - Remove Median Operation

题目大意

思路

为什么这是正确的

相关推荐

评论

题解：AT_arc210_b [ARC210B] Remove Median Operations