题解：AT_arc150_e [ARC150E] Weathercock

wzj33300 · 2025-02-06 14:59:08 · 题解

看到 10^{100}，我们就可以猜测一定在一定轮数内可以变成一种固定的情况。先从 k=1 着手，让我们先写出暴力：

• 一个向左的人 i 转向的条件是：1 到 i 中，向右看的人数减去向左看的人数 >0。
• 一个向右的人 i 转向的条件是：i+1 到 n 中，向左看的人数减去向右看的人数 >0。

很容易可以想到使用前缀和优化，由于条件只需要知道两种人人数的差值，因此我们规定：

此时条件就可以写为：

• 一个向左的人 i 转向的条件是：s_{i-1}-s_0>0，由于 s_0=0 且 s_i-s_{i-1}=-1，条件等价于 s_i\ge0。
• 一个向右的人 i 转向的条件是：-(s_n-s_i)>0，即 s_i>s_n。

现在我们钦定 s_n\ge0，如果不是，那么我们可以把所有的 L/R 取反，再将整个序列翻转，可以证明答案不变。

构建一个坐标系，把所有 (i,s_i) 放到图上并且相邻的连一条线，可以发现，S_i 就决定了 (i-1,s_{i-1}) 到 (i,s_i) 的线段是向上还是向下。

结合上面的条件，我们发现：

1. 所有在 s_n 上方的的线段都要翻转。
2. 在 0 上方的向下线段都要翻转。

如果我们不管第二部分，那么在进行完一轮操作后，s_n 已经成为 s 的最大值，且第二部分的每一次翻转只会把一个后缀的值 +2，所以在进行完一轮操作后，s_n 就是 s 的最大值，后面的操作，向右的人都不会再翻转。

对于向左的人，我们如何判断他会不会翻转？

我们考虑第一个在 0 上方的向下线段（右端点横坐标为 i，s_i\ge0），这条线段要翻转，那么后面的线段的整体高度就会增加 2，下一条向下线段，在这条线段翻转之前的高度至少为 s_i-1，翻转后，高度会变成 s_i+1>0，所以这一条线段一定也会翻转，以此类推，我们可以得到：

• 在进行了一次操作之后得到的 s 数组，对于现在的所有向下线段 i，最终会翻转当且仅当 \max_{1\le j\le i}s_j>0。

现在我们已经有了一个做法，但是这个做法需要我们先做一次把第一部分的处理掉，不好扩展到 k>1，我们希望有一个可以从初始序列直接得到答案的办法。

考虑分析第一部分翻转后会变成什么样。

• 如果 s_n>0，那么第一部分翻转完后，第一个线段（原本肯定向上，翻转后向下）必定在 0 上方，因此会在第二部分中做贡献。
• 如果 s_n=0，那么我们直接特判即可。

现在我们已经可以解决 k=1，考虑扩展，令 N=n\times k。

我们把 s_N 求出来，对于第一部分，考虑 s_i,s_{i+k},s_{i+2k},...，有且只有一个后缀会 \ge s_n，O(1) 把后缀算出来即可。

code