[NOIP2022] 种花

简单前缀和优化 DP，不谈。

[NOIP2022] 喵了个喵

非常高级的构造题。

看到 $k = 2n - 1/2$，我们可能会想到每一个栈内放两个即可，留一个辅助栈，即可完美过掉 $k = 2n - 2$ 的东西。

考虑我们如何处理多出来的那一个。

我们向后考虑，如果一个元素在栈顶有，那么可以直接消掉，但是不在栈顶存在，那么一定在栈底，所以我们必须保留一个空栈使得可以将栈底的他消掉。

设这个只在栈底的元素为 $x$，其头上一定有一个元素 $y$，一个简单的想法是将 $a_i$ 压在 $y$ 头上，自然留下了一个空栈。

但是考虑序列为 $a_i, y, x$ 的情况，此时由于原本的 $y$ 被 $a_i$ 压着，所以只能将新的 $y$ 放入空栈中，但是如此 $x$ 就没法消掉了，这十分恼人。

但是观察到这种情况出现当且仅当 $y$ 在 $a_i - x$ 内的出现次数为奇数，所以我们换一个思路，将 $a_i$ 放在空栈中，这样到 $x$ 的时候，$y$ 也被消完了，此时 $x$ 所在的栈就变成了空栈。

回来考虑偶数次的情况，我们可以在这里面将 $y$ 给消完，所以我们将 $a_i$ 压在 $y$ 上，每次将 $y$ 放在 $a_i$ 上，那么自然到 $x$ 的时候，$x$ 的上面就只有 $y$ 和 $a_i$，并且原本的空栈还是空着的，所以可以将 $x$ 消掉，此时 $y, a_i$ 形成一个新的两个元素的栈。

注意这里新的 $y$ 只能压在 $a_i$ 头上，否则可能影响到原本处于栈顶，但是被 $y$ 压着无法消掉的情况。

按照此规则模拟即可。