| 序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
|---|
同学们现在分散在数轴上 $1 \sim n$ 的整点上，设整点 $i$ 上的同学数量为 $a_i$。
还有一个集合位置的候选集合 $S$ ，初始为 ${1,2,\dots,n}$。
你还要处理 $q$ 次操作，每次操作，可能发生以下事件：
在某个位置的同学增加 $x$ 个或减少 $x$ 个。
令某个区间 $[l,r]$ 内的整点成为可以选择的整点（将 $[l,r]$ 中不在 $S$ 内的点加入 $S$）。
令某个区间 $[l,r]$ 内的整点成为不能选择的整点（将 $S$ 中在 $[l,r]$ 内的点删去）。
对于区间限制的操作，不保证操作前该区间的整点是否能选择。操作的影响都是会保留下来的。
每次操作过后，你都需要找到 $S$ 中的一个整点 $k$ 作为集合位置，最小化所有同学走到该点的距离总和。形式化地，你需要求
$\min_{k\in \mathbb S}\left\{\sum_{i=1}^n a_i\times |i-k|\right\}$
如果有多个满足条件的 $k$，选择 $k$ 最小的那个。