AT_abc467_e [ABC467E] Adjacent Sums (hard)

> 注：C 题题干与 E 题完全相同，仅红色标注的约束条件有区别。 给定两个由 $0$ 以上、$M−1$ 以下整数构成的整数数列 $A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1})$，$A,B$ 的长度分别为 $N$ 和 $N-1$。 你可以对数列 $A$ 执行任意次数下述操作： - 任选一个满足 $1\le i \le N$ 的整数下标 $i$，将 $A_i$ 的值加 $1$。 请求出让数列 $A$ 满足以下条件时，所需要的最少操作总次数。题目保证在给定约束范围内，一定存在可行方案。 需要满足的条件： - 对每一个 $i=1,2,\dots,N-1$，都有 $$(A_i + A_{i+1}) \bmod M = B_i$$ 也就是 $A_i$ 与 $A_{i+1}$ 的和除以$M$，余数等于$B_i$。

以下的形式输入： > $N$ $M$ > $A_1$ $A_2$ $\dots$ $A_N$ > $B_1$ $B_2$ $\dots$ $B_{N-1}$

一行一个整数，表示答案。

### 样例 1 解释 第 $1$ 次操作选择 $i=2$，数组变为 $A=(4,7,7)$。 第 $2$ 次操作选择 $i=1$，数组变为 $A=(5,7,7)$。 第 $3$ 次操作选择 $i=1$，数组变为 $A=(6,7,7)$。 第 $4$ 次操作选择 $i=2$，数组变为 $A=(6,8,7)$。 第 $5$ 次操作选择 $i=1$，数组变为 $A=(7,8,7)$。 $A_1+A_2=7+8=15,A_2+A_3=8+7=15$，满足题目条件。 并且无法通过不超过 $4$ 次的操作达成该条件，因此答案是 $5$。 ### 约束 - $ 2 \leq N \leq 2 \times 10^5 $ - $ \red{3\le M\le10^9} $ - $ 0 \leq A_i \leq M-1 $ - $ 0 \leq B_i \leq M-1 $ - 输入的数均为整数