这个题，非常牛阿。
首先差分一下，把区间操作变为差分数组 \(c\) 上单点 \(\pm a, \pm b\)，要求最后 \(c\) 全为 \(0\)。注意，这里的差分数组是拓展过的，即 \(c_{n + 1} = -c_n\)，要求 \(c_{n + 1}\) 也变为 \(0\)。
令 \(d = \gcd(a, b), A = \frac{a}{d}, B = \frac{b}{d}\)，对于每个 \(c_i\)，我们要求出 \(ax + by = c_i\) 的一组解，如果 \(x > 0\) 则在 \(i\) 上 \(+a\) 的操作数为 \(x\)，如果 \(x < 0\) 则 \(-a\) 的操作数为 \(-x\)，\(y\) 同理。先求出 \(ax + by = d\) 的解 \((u, v)\)，如果 \(d \nmid c_i\) 则无解，否则一组解为 \((x_i, y_i) = (u \times d, v \times d)\)。
我们先不考虑这样的操作序列是否合法，答案为 \(\dfrac{\sum |x_i| + |y_i|}{2}\)，因为操作会两两抵消。由于不考虑是否合法，\((x_i, y_i)\) 是独立的，于是考虑最小化 \(|x_i| + |y_i|\)，我们考虑通解 \((x, y) = (x_i + kB, y_i - kA)\)，不妨设 \(A > B, x > 0, y > A\)，那么我们令 \(x \leftarrow x + B, y \leftarrow y - A\) 一定更优，其它方面也是同理的，我们可以再举一个例子：\(B > A, x < -B, y < 0\)，令 \(x \leftarrow x + B, y \leftarrow y - A\) 也更优。发现了什么？答案一定是最小的非负整数 \(x\)，最大的负整数 \(x\)，最小的非负整数 \(y\)，最大的负整数 \(y\)，所对应的 \(4\) 个解中最小的 \(|x_i| + |y_i|\)。
但是这玩意好像完全没用，因为不合法，但是你别急，我们还有调整法。
令 \(X = \sum x_i, Y = \sum y_i\)，合法当且仅当 \(X = 0\)，这样才能完全抵消。另外因为 \(\sum d_i = 0\)，所以 \(aX + bY = \sum d_i = 0\)，于是 \(X = 0\) 时 \(Y\) 也为 \(0\)。
怎么让 \(X\) 变为 \(0\) 呢，由于 \(AX + BY = 0\)，且 \(A, B\) 互质，所以 \(X\) 一定是 \(B\) 的倍数，即 \(\frac{X}{B}\) 为整数！这个关键观察告诉我们调整的次数是固定的（多调整肯定不会更优），且假如取到最小值的 \((x_i, y_i)\) 满足 \(x_i\) 为最小非负整数或最大负整数，则 \(|x_i| \le B, |X| \le nB\)，否则 \(y_i\) 为最小非负整数或最大负整数，\(|y_i| \le A, |Y| \le nA\)，\(|X| = |\frac{-BY}{A}| \le nB\)，于是最多调整 \(n\) 次。
考虑调整 \((x_i, y_i)\)，如果 \(X < 0\) 就需要让 \(x_i \leftarrow x_i + B, y_i \leftarrow y_i - A\)，反之同理，而这样调整一次增加的代价就是新的 \(|x_i| + |y_i|\) 减去旧的 \(|x_i| + |y_i|\)，优先队列维护即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// typedef __int128 i128;
typedef pair<int, int> pii;
const int N = 2e5 + 10, mod = 998244353;
template<typename T>
void dbg(const T &t) { cout << t << endl; }
template<typename Type, typename... Types>
void dbg(const Type& arg, const Types&... args) {cout << arg << ' ';dbg(args...);
}
namespace Loop1st {
int n;
ll u, v, x[N], y[N], ans, sum, sgn, a, b, c[N], A, B;
priority_queue<pii, vector<pii>, greater<pii>>q;
void update(ll &x, ll &y, ll _x, ll _y) {if (abs(_x) + abs(_y) < abs(x) + abs(y)) x = _x, y = _y;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {if (!b) { x = 1, y = 0; return a; }ll d = exgcd(b, a % b, y, x); y -= a / b * x;return d;
}
void insert(int i) {ll _x = x[i] - sgn * B, _y = y[i] + sgn * A;q.push({abs(_x) + abs(_y) - abs(x[i]) - abs(y[i]), i});
}
void main() {cin >> n >> a >> b;for (int i = 1; i <= n; i++) cin >> c[i];int d = exgcd(a, b, u, v); A = a / d; B = b / d; n++;for (int i = n; i; i--) c[i] -= c[i - 1], x[i] = 1ll << 60;for (int i = 1; i <= n; i++) {if (c[i] % d) {cout << "-1\n";return ;}ll _x = (u * c[i] / d % B + B) % B, _y = (c[i] - _x * a) / b; update(x[i], y[i], _x, _y);_x -= B, _y += A; update(x[i], y[i], _x, _y);_y = (v * c[i] / d + A) % A, _x = (c[i] - _y * b) / a; update(x[i], y[i], _x, _y);_y -= A; _x += B; update(x[i], y[i], _x, _y);sum += x[i];ans += abs(x[i]) + abs(y[i]);}sgn = sum > 0 ? 1 : -1;for (int i = 1; i <= n; i++) insert(i);for (int i = 1; i <= abs(sum / B); i++) {auto [val, id] = q.top(); q.pop();ans += val;x[id] -= sgn * B; y[id] += sgn * A;insert(id);}cout << ans / 2 << '\n';
}}
int main() {// freopen("data.in", "r", stdin);// freopen("data.out", "w", stdout);ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int T = 1;// cin >> T;while (T--) Loop1st::main();return 0;
}
调整法与观察性质的极致利用，妙趣横生。若是意犹未尽，可以去做做冒泡排序。