ABC 440

A B 题都不写了

C

题目大概是说要在一个 $1$ 到 $n$ 的数组间染色，每次染的代价是 $c_i$，然和可以进行两个操作之一：

• 随便选一个 $x$
• 对于 $i$，如果 $(i+x)\ \text{mod}\ (2 \times w) < w$ 就涂黑。

然后让你算最小代价。

思路

很显然，操作 $2$ 会给这个数组分段，每段长为 $2 \times w$，然后我们只用将数组分好，在用滑动窗口算最小值就完了。

D

题目大概意思为：

给你 $n$ 个互不相同的整数，求 $q$ 次询问：每次给定 $x$ 和 $y$，求 $\ge x$ 的整数中，第 $y$ 个不在给定列表里的数是多少。

用二分二分找 $\ge x$ 的整数中，第 $y$ 个不在给定列表里的数，然后二分的左区间为 $l$，右区间为 $x+y+n$ 因为最坏情况下前面 $n$ 个数都被 $a$ 占掉了，check为：

if ((mid - x[i] + 1) - ((upper_bound(a + 1, a + n + 1, mid) - a) - (lower_bound(a + 1, a + n + 1, x[i]) - a)) >= y[i])