这题如果不带修有一个 $O(nV)$ 的倍增做法，但是其实和正解没啥关系。

考虑将相同的数缩成若干个连续段 $(x_1, y_1), (x_2, y_2), \ldots, (x_k, y_k)$。

如果出现了一个谷 $x_{i - 1} > x_i < x_{i + 1}$，那么我们要把两边并起来，至少要把 $x_i$ 变成 $\min(x_{i - 1}, x_{i + 1})$。

设 $d = \min(x_{i - 1}, x_{i + 1}) - x_i$。如果 $2^d \mid y_i$，那么我们可以把 $x_i$ 提升到 $\min(x_{i - 1}, x_{i + 1})$，和两边其中一个合并。

否则两边不可能并起来，把 $(x_i, y_i)$ 分给两边然后继续做，相当于把 $(x_i, y_i)$ 删除，然后插入 $(\min(x_{i - 1}, x_{i + 1}), \left\lfloor\frac{y_i}{2^d}\right\rfloor), (+\infty, 1), (\min(x_{i - 1}, x_{i + 1}), \left\lfloor\frac{y_i}{2^d}\right\rfloor)$。

这样整个序列就变成了一个单峰序列，连续段个数是 $O(V)$ 的。在消除谷的过程中可以把 $x_i + \left\lfloor\log_2 y_i\right\rfloor$ 计入答案。求答案就在序列两端分别添加一个 $+\infty$ 然后不停做上面的过程即可。

发现这个信息是可以合并的，所以可以上线段树支持单点修改。合并两个信息就把右边信息的所有连续段逐个加入到左边信息中。一个连续段添加到一个信息中，就看有没有新产生谷，如果产生了就递归加入新的连续段。

时间复杂度 $O(nV \log n)$，空间复杂度 $O(nV)$。

以下的代码在 QOJ 同时获得了最短解和最优解。

#include <bits/stdc++.h>
using namespace std;

int n, N;

struct node {
	int t, k, a[22][2];
	
	node(int x = 1e9) {
		t = (x < 1e8 ? x : 0);
		a[k = 1][0] = x;
		a[k][1] = 1;
	}
	
	void add(int x, int y) {
		if (!y) {
			return;
		}
		while (k >= 2 && a[k - 1][0] > a[k][0] && a[k][0] < x) {
			int p = a[k][0], q = a[k][1];
			if (a[--k][0] > 1e8 && x > 1e8) {
				continue;
			}
			int d = min(a[k][0], x) - p;
			add(p + d, q >> d);
			if (q & ((1 << d) - 1)) {
				add(1e9, 1);
				add(p + d, q >> d);
			}
		}
		if (k && a[k][0] == x) {
			a[k][1] += y;
		} else {
			a[++k][0] = x;
			a[k][1] = y;
		}
		if (a[k][0] < 1e8) {
			t = max(t, a[k][0] + __lg(a[k][1]));
		}
	}
} a[262199];

inline node operator + (node a, node b) {
	a.t = max(a.t, b.t);
	for (int i = 1; i <= b.k; ++i) {
		a.add(b.a[i][0], b.a[i][1]);
	}
	return a;
}

void prepare_game(vector<int> b) {
	n = (int)b.size();
	N = 1 << (__lg(n + 1) + 1);
	for (int i = 1; i <= n; ++i) {
		a[i + N] = node(b[i - 1]);
	}
	for (int i = N; i; --i) {
		a[i] = a[i << 1] + a[i << 1 | 1];
	}
}

int play_game(int l, int r) {
	node u(1e9), v(1e9);
	for (l += N, r += N + 2; l ^ r ^ 1; l >>= 1, r >>= 1) {
		if (!(l & 1)) {
			u = u + a[l ^ 1];
		}
		if (r & 1) {
			v = a[r ^ 1] + v;
		}
	}
	return (u + v).t;
}

void update_game(int x, int y) {
	a[x += N + 1] = node(y);
	while (x >>= 1) {
		a[x] = a[x << 1] + a[x << 1 | 1];
	}
}