题解：AT_arc150_e [ARC150E] Weathercock

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

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

此时条件就可以写为：

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

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

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

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

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

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

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

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

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

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