题意

给定长 $n$ 的序列 $h_i$ ，每次操作可以使 $h_i\leftarrow h_i-1$ ， $q$ 次询问， 每次给出一个 $X$ , 求使用不超过 $X$ 次操作后 $\sum_{i=1}^{n-1}|h_i-h_{i+1}|+h_1+h_n$ 的最小值。

$n,q\leq5\times10^5,h_i\leq10^{12},X\leq10^{18}$ 。

题解

一个贪心就是，把相邻的相同项都合并，每次选宽长最窄的峰，把它降到相邻大的那个，然后合并。

这个合并可以用链表，似乎还可以用并查集（？），我用了线段树，开三个线段树分别维护每个点所在的块的左端点、右端点、高度。

$\mathcal{O}(n\log n+q)$ 。常数有点大但它开了两秒，两秒内挺稳的。

代码

const int N = 5e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, q;
	ll a[3][N], base;
	struct Question {
		ll val; int id;
		bool operator < (Question &a) const {
			return val < a.val;
		}
	}qt[N];
	ll Ans[N];
	struct Range {
		int l, r; ll val;
		bool operator < (const Range &a) const {
			return (r - l + 1) > (a.r - a.l + 1);
		}
	};
	struct SegmentTree {
		struct Tree {
			int l, r;ll val, tag;
		} t[N << 3];
#define lson (p << 1)
#define rson (p << 1 | 1)
		void Build (int p, int l, int r, int type) {
			t[p].l = l, t[p].r = r;
			if (t[p].l == t[p].r) {
				t[p].val = a[type][l];
				t[p].tag = -1;
				return;
			}
			int mid = (t[p].l + t[p].r) >> 1;
			Build(lson, l, mid, type);
			Build(rson, mid + 1, r, type);
			t[p].tag = -1;
		}
		void pushdown (int p) {
			if (t[p].tag == -1) return;
			t[lson].val = t[lson].tag = t[p].tag;
			t[rson].val = t[rson].tag = t[p].tag;
			t[p].tag = -1;
		}
		void Modify (int p, int l, int r, ll val) {
			if (l <= t[p].l && t[p].r <= r) {
				t[p].val = t[p].tag = val;
				return;
			}
			pushdown(p);
			int mid = (t[p].l + t[p].r) >> 1;
			if (l <= mid) Modify (lson, l, r, val);
			if (r > mid) Modify (rson, l, r, val);
		}
		ll Query (int p, int x) {
			if (x < 1 || x > n) return -1;
			if (t[p].l == t[p].r) return t[p].val;
			pushdown(p);
			int mid = (t[p].l + t[p].r) >> 1;
			if (x <= mid) return Query (lson, x);
			else return Query(rson, x);
		}
	} L, R, Val;
	priority_queue<Range> qu;
	int main () {
		n = Read(), q = Read();
		for (int i = 1; i <= n; i++) {
			a[0][i] = Read();
			base += abs(a[0][i] - a[0][i - 1]);
			a[1][i] = (a[0][i] == a[0][i - 1] && i != 1? a[1][i - 1]: i);
		}
		base += a[0][n];
		for (int i = n; i; i--) a[2][i] = (a[0][i] == a[0][i + 1] && i != n? a[2][i + 1]: i);
		for (int i = 1; i <= n; i = a[2][i] + 1) 
			if (a[0][i] > a[0][i - 1] && a[0][i] > a[0][a[2][i] + 1]) qu.push((Range){i, (int)a[2][i], a[0][i]});
		L.Build(1, 1, n, 1);
		R.Build(1, 1, n, 2);
		Val.Build(1, 1, n, 0);
		for (int i = 1; i <= q; i++) qt[i] = (Question){Read(), i};
		sort (qt + 1, qt + 1 + q);
		int j = 1;
		ll X = 0, ans = 0;
		for (; qt[j].val <= X; Ans[qt[j].id] = 0, j++);
		for (; !qu.empty(); ) {
			Range cur = qu.top(); qu.pop();
			int a = cur.l - 1, b = cur.r + 1;
			ll Va = Val.Query(1, a), Vb = Val.Query(1, b);
//			printf ("%d %d %lld %lld %lld\n", cur.l, cur.r, cur.val, Va, Vb);
			if (Va < Vb) swap(a, b), swap(Va, Vb);
			while (X + (cur.val - Va) * (cur.r - cur.l + 1) >= qt[j].val && j <= q) {
				ll ktimes = (qt[j].val - X) / (cur.r - cur.l + 1);
				ans += ktimes * 2ll;
				Ans[qt[j++].id] = ans;
				cur.val -= ktimes;
				X += ktimes * (cur.r - cur.l + 1);
			}
			if (j > q) break;
			X += (cur.val - Va) * (cur.r - cur.l + 1);
			ans += (cur.val - Va) * 2ll;
			int nl = min((int)L.Query(1, a), cur.l), nr = max((int)R.Query(1, a), cur.r);
			if (Va == Vb) nr = max(nr, (int)R.Query(1, b));
			L.Modify(1, nl, nr, nl);
			R.Modify(1, nl, nr, nr);
			Val.Modify(1, nl, nr, Va);
//			printf ("--> %d %d %lld\n", nl, nr, ans);
			if (nl == 1 && nr == n) {
				while (j <= q) {
					ll ktimes = (qt[j].val - X) / n;
					ans += ktimes * 2ll;
					Ans[qt[j++].id] = ans;
					X += ktimes * n;
				}
				break;
			}
			if (Va > Val.Query(1, nl - 1) && Va > Val.Query(1, nr + 1)) qu.push((Range){nl, nr, Va});
		}
		for (int i = 1; i <= q; i++) printf ("%lld\n", max(base - Ans[i], 0ll));
		return 0;
	}
}

int main () {
//	freopen("ex_block2.in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}