题解：AT_awtf2025_c Get Closer

对于每对球，把左边的视作左括号，右边的视作右括号。题意转化成需要给每个位置填上左右括号，使得段内没有匹配的括号，整个串是一个合法括号串。显然每个段由一段前缀的右括号和一段后缀的左括号构成。

容易想到二分 \(mid\)，判定答案是否 \(\leq mid\)，也就是要求对于每两个相邻的段，前面段的左括号数量加上后面段的右括号数量 \(\leq mid\)。

考虑直接做可行性 DP：令 \(f_{i,x,y}\) 表示考虑了前 \(i\) 段，第 \(i\) 段有 \(x\) 个左括号，前 \(i\) 段共有 \(y\) 个未匹配的右括号，此时是否存在合法方案。转移时枚举第 \(i+1\) 段有 \(v\) 个右括号，需要满足 \(v\leq \min(y,a_{i+1},mid-x)\)，然后 \(f_{i,x,y}\to f_{i+1,a_{i+1}-v,y+a_{i+1}-2v}\)。不难注意到 \(x\) 的唯一作用是判定 \(v\) 是否合法，显然 \(x\) 越小限制越松。使用经典的换维技巧，把 \(x\) 换到答案上：令 \(f_{i,y}\) 表示能取到的最小的 \(x\)。最后只需要判断是否有 \(f_{n,0}=0\)。此时状态数为 \(\mathcal{O}(nS)\)，可以做到 \(\mathcal{O}(nS^2\log{S})\)。

感觉不太好优化了。观察一下 DP 数组的性质，我们指出：

• \(f_{i,y}\) 有值的位置是隔位连续的，形如 \(L,L+2,\cdots,R\)。
• \(\forall y=L+2,\cdots,R,0\leq f_{i,y}-f_{i,y-2}\leq 1\)。

证明

使用归纳法。\(i=1\) 时只有 \(f_{1,a_1}=a_1\)，命题成立。

现在假设 \(f_{i,y}\) 满足我们的性质。考察我们的转移：枚举 \(v\leq \min(y,a_{i+1},mid-f_{i,y})\)，令 \(a_{i+1}-v\to f_{i+1,y+a_{i+1}-2v}\)。

\(a_{i+1}-2v\) 奇偶性固定，于是 \(f_{i+1,y}\) 显然满足第一条性质。

对于第二条性质，不妨先改写一下转移形式。考虑哪些 \(v\) 能转移到 \(f_{i+1,y}\)，那么原条件可以写作 \(v\leq \min(mid-f_{y-a_{i+1}+2v},a_{i+1},y-a_{i+1}+2v)\)，整理可以得到：

\[a_{i+1}-y\leq v\leq \min(a_{i+1},v_R) \]

其中

\[v_R=\max_{v\leq mid-f_{i,y+2v-a_{i+1}}}v \]

那么实际上转移就是 \(a_{i+1}-\min(a_{i+1},v_R)\to f_{i+1,y}\)。

观察到不断令 \(y\gets y+2\) 的过程中，\(v_R\) 单调不增，这就证明了 \(f_{i,y}\geq f_{i,y-2}\)。进一步地，考虑 \(f_{i,y}\) 对应的 \(v_R\)，可以得到 \(v_R\leq mid-f_{i,y+2v_R-a_{i+1}}\)，考察 \(f_{i,y+2}\)，那么 \(v_R-1\leq mid-f_{i,y+2+2(v_R-1)-a_{i+1}}=mid-f_{i,y+2v_R-a_{i+1}}\)，因此 \(v_R-1\leq v_R'\leq v_R\)，于是 \(f_{i,y}-f_{i,y-2}\leq 1\) 也得证。\(\Box\)

这告诉我们 \(f_{i,y}\) 的定义域是有空隙的，而值域是连续的。据此考虑转置维度，令 \(g_{i,x}=\max\limits_{f_{i,y}\leq x}y\)，则转置后 \(g_{i,x}\) 的定义域是连续的。转移时直接枚举 \(v\leq \min(a_{i+1},mid)\)，考虑如何更新 \(g_{i+1,a_{i+1}-v}\)，限制条件为 \(f_{i,y}\leq mid-v\land y\geq v\)。因此转移时若 \(g_{i,mid-v}\geq v\) 则令 \(g_{i,mid-v}\to g_{i+1,a_{i+1}-v}\) 即可。更新完需要做一次前缀最大值。这样 DP 部分的时间复杂度就优化到了 \(\mathcal{O}(nS)\)。

有个问题，转置维度后如何判断最终是否合法？考虑到转置维度相当于交换定义域与值域，而原本的判断条件等价于 \(f_{i,y}\) 的定义域与值域下界都为 \(0\)，因此用同样的条件判断 \(g\) 即可。定义域只需判断 \(g_{n,0}\neq -\infty\)，但是值域则不能直接判断 \(g_{n,0}=0\)。我们在 DP 过程中同时维护值域下界 \(L\) 即可。

$\mathcal{O}(nS)$ DP 的参考代码

bool dp(int mid) {fill(g[0], g[0] + mx + 1, -inf);fill(g[1], g[1] + mx + 1, -inf);fill(g[1] + a[1], g[1] + mx + 1, a[1]);int L = a[1];for (int i = 1; i < n; ++i) {int cur = i & 1, nxt = cur ^ 1;int mn = inf;for (int v = 0; v <= min(mid, a[i + 1]); ++v)if (g[cur][mid - v] >= v) {chk_max(g[nxt][a[i + 1] - v], g[cur][mid - v] + a[i + 1] - v * 2);chk_min(mn, max(L, v) + a[i + 1] - v * 2);}L = mn;if (L == inf) return 0;for (int v = 1; v <= mx; ++v) chk_max(g[nxt][v], g[nxt][v - 1]);fill(g[cur], g[cur] + mx + 1, -inf);}return !L && g[n & 1][0] != -inf;
}

进一步优化，观察 DP 本质上是在做什么：

1. 更新时有用的 \(x\) 范围为 \([\max(mid-a_{i+1},0),mid]\)，于是把 \(g_{i,x}\) 的定义域截断到这个区间内。
2. \(g_{i,mid-v}\geq v\Leftrightarrow g_{i,x}+x\geq m\)，显然 \(g_{i,x}+x\) 单调递增，因此合法的 \(x\) 是一段后缀，可以进一步去掉定义域的一个前缀。
3. \(g_{i,mid-v}+a_{i+1}-2v\to g_{i+1,a_{i+1}-v}\)，相当于 \(g_{i,x}+2x+a_{i+1}-2mid\to g_{i+1,x+a_{i+1}-mid}\)。那么相当于给差分数组全局 \(+2\)，然后函数向上平移 \(a_{i+1}-2mid\) 个单位，再向右平移 \(a_{i+1}-mid\) 个单位。
4. 由于最后做了个前缀最大值，需要把函数定义域上界拓展到 \(mx\)。

容易想到维护起始点并且使用双端队列维护差分数组连续段。第 \(1\) 步的截断是容易维护的，第 \(2\) 步的截断可以从前往后依次考虑每个连续段，右端点不合法就直接扔掉，否则可以根据对应的一次函数 \(\mathcal{O}(1)\) 算出截断点。第 \(3\) 步的操作可以打加标记和平移起始点，第 \(4\) 步的操作相当于在最后接上一段水平线段。这样我们就把 DP 做到了 \(\mathcal{O}(n)\)。总体时间复杂度为 \(\mathcal{O}(n\log{V})\)。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long;
using i128 = __int128;
using ui = unsigned int;
using ull = unsigned long long;
using u128 = unsigned __int128;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 2.5e5 + 5;template<typename T> inline T lowbit(T x) { return x & -x; }
template<typename T> inline void chk_min(T &x, T y) { x = y < x ? y : x; }
template<typename T> inline void chk_max(T &x, T y) { x = x < y ? y : x; }int tc;
int n, mx, a[N];
int hd, tl; pll q[N];bool dp(ll mid) {hd = 1, tl = 0;ll pos = a[1], val = a[1], L = a[1], tg = 0;q[++tl] = {mx - a[1], 0};for (int i = 1; i < n; ++i) {while (hd <= tl && pos < mid - a[i + 1]) {auto &[len, df] = q[hd];ll d = min<ll>(len, mid - a[i + 1] - pos);pos += d, val += d * (df + tg);len -= d;if (!len) ++hd;}ll del = mx - mid;while (hd <= tl && del > 0) {auto &[len, df] = q[tl];ll d = min(del, len);len -= d, del -= d;if (!len) --tl;}while (pos + val < mid) {if (hd > tl) return 0;auto &[len, df] = q[hd];ll cnt = (mid - pos - val + df + tg) / (df + tg + 1), d = min(cnt, len);pos += d, val += d * (df + tg);len -= d;if (!len) ++hd;}if (pos > mid) return 0;ll v = mid - pos;L = max(L, v) + a[i + 1] - v * 2;tg += 2;if (mx > a[i + 1]) q[++tl] = {mx - a[i + 1], -tg};pos += a[i + 1] - mid, val += a[i + 1] - v * 2;}return !L && !pos;
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> tc;while (tc--) {cin >> n;for (int i = 1; i <= n; ++i) cin >> a[i];mx = (*max_element(a + 1, a + n + 1)) << 1;ll l = 1, r = mx, mid;while (l < r) dp(mid = l + r >> 1) ? r = mid : l = mid + 1;cout << l << '\n';}return 0;
}