CF1923C题解

瞪眼出结论题

结论

先考虑只有一次询问的情况。

我们要构造一个序列 $b$。

1. 如果 $c_i$ 是 $1$，那么 $b_i$ 取 $2$。
2. 否则，$b_i$ 取 $1$。

这样就能做到 $\Sigma b$ 尽量小。

如果 $\Sigma b \le \Sigma c$,那么肯定是可以通过一些骚操作满足条件的。否则再怎么样也不行，毕竟 $\Sigma b$ 已经尽量小了。

这样我们就胡出了一个 $\Theta(n)$ 的算法。

---

实现

为了实现多次询问，要用前缀和优化。

代码很简单的啦。

不过不知道为什么，有人不开 long long 被 Hack，我不开 long long 却是没过 pretest。