显然平衡序列的长度必须是 $2^k - 1$ 的形式，所以有可能成为平衡序列的区间只有 $\mathcal{O}(n \log n)$ 个，考虑暴力维护这些区间的平衡状态。

对于一个长度为 $2^k - 1$ 的区间，若其合法状态改变，要么其中点或者左右两部分的某个中点被修改，要么左右两部分平衡状态有更新。按照 $k$ 从小到大处理这些变化，每一个 $k$ 记录下相应变化的区间是哪些，在 $k + 1$ 处处理即可。

注意到平衡序列有性质：中点处的数一定是整个序列的严格最大值。而对于一个 $k$，受影响的区间只有在修改位置附近的 $\mathcal{O}(2^k)$ 个，所以可能作为严格最大值的位置只有 $\mathcal{O}(1)$ 个。那么每一个 $k$ 的修改数量也是 $\mathcal{O}(1)$ 的。

所以单次修改的时间复杂度为 $\mathcal{O}(\log n)$。