ABC281E 题解
_dijkstra_
·
·
题解
打完去讨论区看了一下，大家这题都打的平衡树有关算法。
实际上，本题暴力 vector 插入可过。
以下做法可通过赛时数据，不保证会被 hack 掉。
思路
暴力也不是纯暴力，想到类似一个滑动窗口的方法：
对于 i \le m 的情况，由于不需要删除元素（后面会讲），所以直接暴力 insert 即可。
对于 $i > m$ 的情况，如下图所示：
现在我们要加入新的元素 $val_i$（相当于区间滑动了一格）。
这里会有两种情况。情况一：
这种情况不需要做任何事，只用暴力插入。
情况二：
这种情况，$sum$ 变为 $sum + val_i - a_k$。
---
那么除了插入，还有删除呢！我们要删除 $val_{i - m}$。
这个是同理的，就不画图了：
+ 如果对答案没有影响，直接删除即可。
+ 如果有影响，$sum$ 变为 $sum - a_{pos} + a_{k + 1}$，即删除元素并容下备选的元素。
## 代码
为何暴力 `vector` 插入跑得飞快呢？
+ 数据范围较小，只有 $2\times 10^5$。
+ 不是 Ynoi 题，数据也没有卡到极限数据（？）。
+ `vector` 插入、删除，**常数很小很小**。
有不少题（如 [P1627](https://www.luogu.com.cn/problem/P1627)）都是可以暴力 `vector` 过掉的。
```cpp
int val[200005];
void solve()
{
vector <int> a; a.pb(-1); //vector 下标从 0 开始，但是我习惯下标从 1 开始
int n, m, k;
ll sum = 0; //注意 long long
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
{
scanf("%d", &val[i]);
if (i <= m) //还不需要删除，直接暴力 insert
{
a.insert(lower_bound(a.begin(), a.end(), val[i]), val[i]);
if (i == m) {for (int j = 1; j <= k; j++) sum += a[j];} //计算一下 sum，方便滑动
}
else
{
int pos = lower_bound(a.begin(), a.end(), val[i]) - a.begin(); //插入的位置
if (pos <= k) sum += val[i] - a[k]; //如果对答案有影响，加上 val[i] 并挤掉当前的 a[k]
a.insert(a.begin() + pos, val[i]); //暴力插入
pos = lower_bound(a.begin(), a.end(), val[i - m]) - a.begin(); //删除的位置
if (pos <= k) sum += - a[pos] + a[k + 1]; //如果对答案有影响，减去 a[pos] 并容下当前的 a[k+1]
a.erase(a.begin() + pos); //暴力删除
}
if (i >= m) printf("%lld ", sum); //输出答案即可
}
puts("");
}
```