[ARC130E] Increasing Minimumm
？
考虑模拟一下题目中的过程，发现相当于将原序列按照初始值划分为若干个等价类，然后每次都会先合并等价类然后重排等价类中的所有数并加入 \(I\) 中。这样将 \(I\) 划分成了若干段。
考虑假设我们一共划分出 \(T\) 个段，那么最终每个数的答案就是 \(T\) 减去 \(i\) 出现的次数，当然最终我们假设每个数都至少出现了一次，如果某些数没出现过就假装它出现过。
然后发现只需贪心地让划分的总段数最小并且最后一段最大即可。有一个贪心的想法是尽可能长的划分每一段，可惜无解判错了，直接上个 dp 就做完了。
复杂度 \(O(N + K)\)。
int main() {
read(n, k);
for(int i = 1; i <= k; ++i)
read(a[i]), ++cnt[a[i]];
int pre = 0;
for(int i = 1, tot = 0; i <= k; ++i) {
pre = max(pre, lst[a[i]]);
if(!lst[a[i]]) ++ tot;
lst[a[i]] = i;
if(pre == i - tot) f[i] = f[pre] + 1;
else f[i] = inf;
}
f[k + 1] = inf;
int pos = k + 1;
for(int i = pre; i <= k; ++i)
if(f[i] <= f[pos])
pos = i;
if(f[pos] == inf) {
puts("-1");
return 0;
}
for(int i = pos + 1; i <= k; ++i)
vis[a[i]] = 1;
for(int i = 1; i <= n; ++i)
printf("%d ",cnt[i] ? f[pos] - cnt[i] + vis[i] + 1 : f[pos] + 1);
puts("");
}