题解：P12649 [KOI 2024 Round 2] 收集彩球
本篇题解提供一种学数据结构学傻了的数据结构模拟贪心策略解法。又臭又长，不如图论解法与证法。
首先手玩几个样例，发现要使得两个同色球能在操作后放在一个桶中，操作前这两个球必须均位于不同的桶的顶端。
当有两个同色球位于不同桶顶端时，存在以下几种操作：
1. 两个球，均在桶的上方位置，此时需要有一个空桶才能使得两个球放到同一个桶当中，操作次数为 2。
2. 两个球，一个在桶的上方位置，一个在桶的下方位置，此时把在一号位置的球放在位于二号位置的球的桶中，操作次数为 1。
3. 两个球，均在桶的下方位置，此时可以把两个球放到同一个桶当中，然后得到一个空桶，操作次数为 1。
然后考虑并分讨一下是否存在空桶的情况：
- 当存在空桶的时候，优先进行 1 操作。本种情况下，因为存在空桶，所以必定所有桶内都存着两个球，无法进行 2 操作与 3 操作，但是我们可以通过实现 1 操作来创造可以进行 2 操作与 3 操作的情况，使得操作可以继续进行。
- 当不存在空桶的时候，2 操作与 3 操作有只一种能够进行，直接进行即可。本种情况下，如果能进行 2 操作，则说明两个只有一个球的桶中的球的颜色是不同的，无法进行 3 操作，如果能进行 2 操作，则说明两个只有一个球的桶中的球的颜色是相同的，无法进行 2 操作。因此我们从其中取一种可进行的操作进行即可。
但是会存在球都被错开的情况，此时三种操作均无法进行，且一种颜色的球只会在顶端出现一次，如：桶一从上到下存颜色为
考虑证明：
对于给出初始状态当中下方的一个球，当且仅当上方没有球，并且有另一个在顶端的球时，能进行匹配，对于这种状态，我们可以用 1 操作来创作出一种两个球均在桶的上方的局面，在进行过若干次 2 操作后，由一个 3 操作来结尾，因为每个球只出现两次，所以每种颜色的球只会产生两个桶的对应关系，即本次与下次操作的桶，当我们最后剩余两个同色球在不同桶时，我们会进行一次 3 操作，使得形成一个新的有若干球匹配完成的状态。
排除掉已经匹配完成的球，就到了一个新的初始状态，我们可以继续使用 1 操作来创造出进行 2 操作与 3 操作的局面，直至所有球被匹配完成为止。
而当其产生所有球被错开的情况，相当于我们进行一次把上方的球取出的时候，我们可以借助一个空桶移开一个元素，使得其到达可进行 2 操作的情况，并一直进行 2 操作直至所有球被匹配完成为止，也会形成一个新的有若干球匹配完成的状态。
考虑无解的情况，此时产生了多个 1 操作或对应到了一连串 2 操作上，又或是无法进行 1 操作，而同色球在不同桶中而不是一对一错开的情况，因为第一步的操作（包含两种情况）需要空桶的支持，这两种情况下只有一个空桶无法满足需求，所以无解。
因此每次选择只与进行 1 操作来进行匹配并已 3 操作作为结尾或是选择错开的情况进行匹配有关，并且每次进行完会形成新的子状态，并形成独立问题，因此策略正确。
发现需要维护一种数据结构来维护球有多少在最顶端，支持查询全局最大值，单点修改，并且需要维护不同情况下的策略，这里我采用了线段树。
整体复杂度
代码实现丑，较上方描述略为复杂，慎看。
代码