题外话

• 本题中文名“石墨烯”纯属出题人夹带私货，与题目无关，具体含义不便透露，大家不要过度解读。
• 本题原来只有 $k=0$ 这个版本作为签到，但是因为某些原因需要稍微加强难度，就变成了现在这个版本。

Description

• 给定长为 $n$ 的序列 $a, b$，每轮操作先使每对 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差，然后使 $a$ 循环右移一位。
• 操作开始前，可以先对 $a$ 进行 $k$ 次 $a_i \leftarrow a_{i-1}$（需保证 $a_i$ 恒非负），问最少几轮操作才能使 $a$ 全变为零？
• $1 \le n, \sum{n} \le 5 \times 10^5$，$1 \le a_i, b_i \le 10^9$。

$k=0$

• 考虑对于每个 $a_i$ 分别求出至少循环右移几次之后会变为零，记之为 $d_i$，则答案即为 $\max_{1≤\le i \le n}{d_i}$。
• 遇到环上问题，首先考虑断环为链（即令 $a_{i+n}=a_i,b_{i+n}=b_i$）。

• 考虑如下转化：记 $s$ 为由 $a_1$ 个左括号，$b_1$ 个右括号，$a_2$ 个左括号，$b_2$ 个右括号，……，$a_{2n}$ 个左括号，$b_{2n}$ 个右括号顺次拼接而成的括号串，则原题中的操作过程就相当于对 $s$ 进行括号匹配的过程，而 $a_i$ 会被哪个 $b_j$ 首次消成零，就取决于 $a_i$ 对应的第一个左括号所匹配的右括号属于哪个 $b_j$ 。

  • “使 $(a_i, b_i)$ 中较小值变为零，较大值变为它们的差” $\rightarrow$ “匹配 $a_i, b_i$ 对应的括号”；
  • “使 $a$ 循环右移一位” $\rightarrow$ “未被匹配的左括号继续向右寻找右括号尝试匹配”。
• 对于括号匹配问题，自然想到利用前缀和转化。
• 令 $c_i=\sum_{j=1}^{i}(a_i-b_j)$，记 $p_i$ 为最小的满足 $p_i > i$ 且 $c_{p_i} \le c_i$ 的下标，则 $d_i$ 即为 $p_i-i$。
• 使用单调栈即可求出所有 $p_i$，时间复杂度为 $O(\sum n)$。

正解

• 加入了 $k$ 的限制后，考虑二分答案 $x$，转而求在 $x$ 轮操作后将 $a$ 全变为零的最少 $-1$ 次数。
• 发现直接在断环为链的 $2n$ 个数上不太好计算贡献（因为可能会重复计算），所以我们进行如下调整：将 $a,b$ 同时循环右移若干位，使得 $a_i-b_i$ 的前缀和 $c_i$ 的最小值在 $c_n$ 处取到。
• 这样调整的好处是，对于调整后的 $a,b$，我们所关心的 $p_i(1 \le i \le n)$ 都不会超过 $n$，也就是说，在实际操作过程中，不会出现 $a_n > 0$ 右移到 $a_1$ 的情况。
• 因此，我们仅通过调整 $a, b$ 就将环上问题转化为了一个长为 $n$ 的链上问题。
• 接下来考虑如何在调整后的 $a,b$ 上计算答案为 $x$ 时的最少 $-1$ 次数。
• 不难想到对 $a$ 从 $n-x$ 到 $0$ 使用贪心，若当前位置 $i$ 对应的 $d_i=p_i-i > x$，即若 $\min_{j=i+1}^{i+x}{c_j} > c_i$，则对 $a_{i+1}$ 进行 $\min_{j=i+1}^{i+x}{c_j} - c_i$ 次 $-1$。
• 整个过程均可通过单调栈维护。
• 时间复杂度为 $O(\sum n \log k)$。