很有意思的一道题。
思路
首先将相邻一样的数合并，每个元素变成一个二元组，表示数与出现次数。
考虑什么时候不能合并。
我们发现假如充分合并后，现在有连续的三个数 \(x_1,x_2,x_3\)，以及他们各自的出现次数 \(y_1,y_2,y_3\)。
如果 \(x_1>x_2,x_3>x_2\)。
我们想要合并这三个，必须要先把 \(x_2\) 合并成 \(\min(x_1,x_3)\)。
但是如果做不到的话，那么这三个数就一定不可能合并了。
相当于整个序列从这里断开了。
这样的话，整个序列是一堆单峰序列。
考虑末尾追加一个二元组 \((x,y)\) 会有什么影响：
-
序列尾部元素与 \(x\) 相等。
累加 \(y\) 即可。
-
序列元素少于两个。
直接插入即可。
-
序列尾部大于 \(x\), 或尾部大于倒数第二个。
同样直接插入即可。
-
除了以上情况，我们就需要一些处理了。
将末尾与倒数第二个提出来，记为 \((x_1,y_1),(x_2,y_2)\)。
首先我们判断能否将 \(x_1\) 提升至 \(\min(x,x_2)\)，如果可以，我们就先将其提升，然后再递归插入。
如果不可以，我们可以插入一个极大值作为分割符，然后将 \(x_1\) 的贡献往 \(x\) 与 \(x_2\) 上累加，再递归插入。
线段树维护即可。
时间复杂度：\(O(nv\log n)\)。
Code
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100010];
struct Node {
int ns = 0;
vector<pair<int, int>> cr{};
inline void init(int x) { vector<pair<int, int>>{{x, 1}}.swap(cr); ns = x; }
inline void add(pair<int, int> x) {
if (x.second) ns = max(ns, x.first + __lg(x.second));
if (cr.size() && cr.back().first == x.first) {
cr.back().second += x.second;
if (cr.back().second)
ns = max(ns, cr.back().first + __lg(cr.back().second));
}
else if (cr.size() <= 1)
cr.push_back(x);
else if (cr.back().first > x.first)
cr.push_back(x);
else if (cr.size() >= 2 && cr.back().first > cr[cr.size() - 2].first)
cr.push_back(x);
else {
auto y = cr.back();
cr.pop_back();
auto z = cr.back();
int d = min(30, min(x.first, z.first) - y.first);
if ((y.second & (-y.second)) >= (1 << d))
add({y.first + d, y.second >> d}), add(x);
else {
if (__lg(y.second) >= z.first - y.first)
add({z.first, y.second >> (z.first - y.first)});
add({1e9, 0});
if (__lg(y.second) >= x.first - y.first)
x.second += y.second >> (x.first - y.first);
add(x);
}
}
}
inline friend Node operator+(Node a, Node b) {
Node c = a;
c.ns = max(b.ns, c.ns);
for (auto i : b.cr) c.add(i);
return c;
}
} ns, d[200010];
inline void build(int p, int l, int r) {
if (l == r) d[p].init(a[l]);
else {
int mid = (l + r) >> 1;
build(mid<<1, l, mid);
build(mid<<1|1, mid + 1, r);
d[p] = d[mid<<1] + d[mid<<1|1];
}
}
inline void upd(int p, int l, int r, int k) {
if (l == r) d[p].init(a[l]);
else {
int mid = (l + r) >> 1;
if (mid >= k) upd(mid<<1, l, mid, k); else upd(mid<<1|1, mid + 1, r, k);
d[p] = d[mid<<1] + d[mid<<1|1];
}
}
inline void ask(int p, int l, int r, int L, int R) {
if (L <= l && r <= R) ns = ns + d[p];
else {
int mid = (l + r) >> 1;
if (L <= mid) ask(mid<<1, l, mid, L, R);
if (mid < R) ask(mid<<1|1, mid + 1, r, L, R);
}
}
void prepare_game(vector<int> A) {
n = A.size();
for (int i = 1; i <= n; i++) a[i] = A[i - 1];
build(1, 1, n);
}
int play_game(int l, int r) {
ns.cr.clear();
ns.ns = 0;
ns.add({1e9, 0});
ask(1, 1, n, l + 1, r + 1);
ns.add({1e9, 0});
return ns.ns;
}
void update_game(int p, int v) {
a[p + 1] = v;
upd(1, 1, n, p + 1);
}