题解：AT_abc448_c [ABC448C] Except and Min

tangtianyao0123 · 2026-03-07 22:56:05 · 题解

题目传送门。

我们考虑先将 a_i 带编号排序。然后对于每次询问，从前往后遍历 a，如果当前的 a_i 的原本位置没有被删除的话就直接输出答案。

这样子的复杂度看似是 O(nq+n\log n) 的。但是我们先分析一下就知道循环 k 次必出答案。否则的话就意味着前 k+1 个数都被删除了。但由于只有 k 个数被删除，因此只会循环 k 次。由于 k\leq5，所以我们可以把每一次循环的复杂度看成 O(1) 的，因此时间复杂度就是 O(n\log n+q) 的。