题解：AT_arc202_a [ARC202A] Merge and Increment

WaterM · 2025-12-31 21:52:04 · 题解

显然的贪心是，先处理出来值相同的连续段，然后按照值域从小到大处理。对于一个连续段，把他的长度变成除以二向上取整，答案变量加上它模二（也就是，如果原来长度是奇数就需要一个插入一个数垫一下）。

然后维护这个事情可以用一个堆和链表维护。链表干的事情是，合并值相同的连续段。堆干的事情是取出值最小的连续段。

然后每次连续段的长度是会减半的，所以每种最多操作 O(\log V) 次。特殊地，连续段长度为 1 就 O(1) 特判合并。

最终的复杂度是 O(n\log n\log V)。