- Missing Subarray Sum (缺失的子数组和)

---

一、题目回顾

给定一个回文正整数数组 $a$，长度为 $n$。 现在给出所有子数组和，恰好缺失一个，让你还原出这个回文数组。

总子数组数量：$\boldsymbol{\dfrac{n(n+1)}{2}}$。

---

二、核心性质

设 $a$ 是回文正数数组。 对于任意子数组 $[l,r]$，它的对称子数组是：

$$[n+1-r,\ n+1-l]$$

因为 $a$ 回文，所以这两个子数组的和相等。

---

1. 非中心子数组

如果 $[l,r]$ 不是中心对称的（即 $l+r \neq n+1$）， 那么它和对称子数组是两个不同子数组，因此它们的和一定出现偶数次。

2. 中心子数组（关键）

满足 $l+r = n+1$ 的子数组叫中心子数组。 它们自己和自己对称，因此只出现一次。

又因为所有数都是正数，更长的中心子数组一定包含更短的，所以： 中心子数组的和严格递增，互不相同。

---

三、核心结论

在完整的子数组和列表中：

出现奇数次的值 = 全部中心子数组的和 数量恰好为：$\boldsymbol{\left\lceil \dfrac{n}{2} \right\rceil}$

---

四、如何用中心和还原数组

把所有中心子数组的和从小到大排序：

$$c_1 < c_2 < \dots < c_m,\quad m=\left\lceil\dfrac n2\right\rceil $$

还原规则：

1. $c_1$：最中心元素（奇数 $n$）或中间两数之和（偶数 $n$）。
2. $c_k - c_{k-1}$：向外扩展一对相等元素的和。
3. 每一层向外扩展的数为：$\boldsymbol{\dfrac{c_k - c_{k-1}}{2}}$。

---

五、如何找到缺失的和

我们现在拿到的是缺一个和的列表。

设 $m = \left\lceil \dfrac n2 \right\rceil$。

情况 1：缺失的是中心子数组和

此时出现奇数次的值的数量为：

$$m-1$$

我们用这些值构造一个长度为 $n-2$ 的回文数组 $b$。

情况 2：缺失的是非中心子数组和

此时出现奇数次的值的数量为：

$$m+1$$

我们用这些值构造一个长度为 $n+2$ 的回文数组 $b$。

---

六、标程统一公式（最强结论）

设：

• $x$ = 删掉 $b$ 的所有子数组和后，剩下的最大值
• $y$ = 数组 $b$ 的总和

则缺失的子数组和为：

$$\boldsymbol{missing} = 2x - y$$

---

七、完整算法流程

步骤 1

统计输入中每个数的出现次数，收集出现奇数次的值。

步骤 2

设 $m = \lceil n/2 \rceil$。

• 若奇数个数 $= m-1$ → 缺失中心和
• 若奇数个数 $= m+1$ → 缺失非中心和

步骤 3

根据情况构造辅助数组 $b$（长度 $n-2$ 或 $n+2$）。

步骤 4

用公式计算缺失和：

$$missing = 2x - y$$

步骤 5

把 $missing$ 加回输入列表，得到完整子数组和。

步骤 6

重新提取中心和，还原出原回文数组 $a$。

---

八、复杂度

$$O(n^2\log n)$$

完全满足 $n \le 1000$。

---

九、极简总结

1. 回文数组的子数组和里，只有中心子数组和出现奇数次。
2. 根据奇数次数值的数量，判断缺失类型。
3. 构造辅助数组 $b$，用公式 $\boldsymbol{2x-y}$ 求出缺失和。
4. 补全后用中心和序列唯一还原回文数组。
5. 解法唯一、正确、高效。

---

十、代码

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

vector<ll> build_pal(const vector<ll>& cents) {
    int m = cents.size();
    vector<ll> arr;
    if (m == 0) return arr;

    ll mid = cents[0];
    if (m == 1) {
        arr = {mid};
        return arr;
    }

    vector<ll> pairs;
    for (int i = 1; i < m; ++i) {
        ll d = cents[i] - cents[i-1];
        pairs.push_back(d / 2);
    }
    reverse(pairs.begin(), pairs.end());
    arr = pairs;
    arr.push_back(mid);
    arr.insert(arr.end(), pairs.rbegin(), pairs.rend());
    return arr;
}

vector<ll> get_subarray_sums(const vector<ll>& a) {
    vector<ll> res;
    int n = a.size();
    for (int l = 0; l < n; ++l) {
        ll cur = 0;
        for (int r = l; r < n; ++r) {
            cur += a[r];
            res.push_back(cur);
        }
    }
    return res;
}

ll find_missing(int n, const vector<ll>& s) {
    map<ll, int> cnt;
    for (ll x : s) cnt[x]++;
    vector<ll> odd;
    for (auto& p : cnt)
        if (p.second % 2 != 0)
            odd.push_back(p.first);
    sort(odd.begin(), odd.end());

    int m_ideal = (n + 1) / 2;
    int len_b;
    vector<ll> cents_b = odd;

    if ((int)odd.size() == m_ideal - 1) len_b = n - 2;
    else len_b = n + 2;

    vector<ll> b = build_pal(cents_b);
    vector<ll> sum_b = get_subarray_sums(b);

    multiset<ll> ms(s.begin(), s.end());
    for (ll x : sum_b) {
        auto it = ms.find(x);
        if (it != ms.end()) ms.erase(it);
    }

    ll x = *ms.rbegin();
    ll y = accumulate(b.begin(), b.end(), 0LL);
    return 2 * x - y;
}

vector<ll> solve(int n, vector<ll> s) {
    ll miss = find_missing(n, s);
    s.push_back(miss);

    map<ll, int> cnt;
    for (ll x : s) cnt[x]++;
    vector<ll> cents;
    for (auto& p : cnt)
        if (p.second % 2 != 0)
            cents.push_back(p.first);
    sort(cents.begin(), cents.end());
    return build_pal(cents);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int sz = n * (n + 1) / 2 - 1;
        vector<ll> s(sz);
        for (auto& x : s) cin >> x;
        auto ans = solve(n, s);
        for (ll x : ans) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}