Range Reconstruction (USACO Silver 2022 December)

$r[i][i+1] = |a_{i+1} - a_i|$
很容易发现，我们总可以不失一般性地令 $a_1 = 0,\, a_2 = r[1][2]$
已知 $a_i$ ，则 $a_{i+1}$ 只有两种可能： $a_{i+1} = a_i + r[i][i+1]$ 或 $a_{i+1} = a_i - r[i][i+1]$
已知 $a_i,\, a_{i+1}$ ，能否容易地确定 $a_{i+2}$ ？答案是可以。
- 如果 $a_{i+1} > a_i$ ，可以证明当 $a_{i+2} = a_{i+1} + r[i+1][i+2]$ 时， $r[i][i+2]$ 更大
- 如果 $a_{i+1} < a_i$ ，则当 $a_{i+2} = a_{i+1} - r[i+1][i+2]$ 时， $r[i][i+2]$ 更大
因此， $r[i][i+2]$ 在选择 $+$ 或 $-$ 时会有不同的值，所以我们可以分别尝试两种情况，看看哪种能生成正确的 $r[i][i+2]$
如果 $a_{i+1} = a_i$ 怎么办？那么我们需要向左寻找 $j < i$ ，使得 $a_j \neq a_{i+1}$ ，并且 $a_j,\, a_{i+1},\, a_{i+2}$ 之间满足上述关系。

换句话说，我们收集所有 $a[x_i] \neq a[x_{i+1}]$ 的下标，然后用 $r[x_i][x_{i+2}]$ 和 $r[x_{i+1}][x_{i+2}]$ 来确定 $a[x_{i+2}]$

时间复杂度 $O(N)$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
int a[305];
int r[305][305];
vector<int> x;   // stores all indexes where a[x[i]] != a[x[i]+1]
int bottom;
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            scanf("%d", &r[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i == 1 || r[i-1][i] != 0) {
            x.push_back(i);
        }
    }
    if (x.size() >= 2) a[x[1]] = r[x[0]][x[1]];
    for (int i = 2; i < x.size(); i++) {
        int j = x[i-2];
        int k = x[i-1];
        int l = x[i];
        int mx = max(a[j], a[k]);
        int mn = min(a[j], a[k]);
        int mx2 = max(mx, a[k] + r[k][l]);
        int mn2 = min(mn, a[k] + r[k][l]);
        if (mx2 - mn2 == r[j][l])
            a[l] = a[k] + r[k][l];
        else
            a[l] = a[k] - r[k][l];
        bottom = min(bottom, a[l]);    // avoid printing negative values
    }
    for (int i = 1; i <= n; i++) {
        if (i > 1 && r[i-1][i] == 0) a[i] = a[i-1];
        printf("%d%c", a[i] - bottom, i == n ? '\n' : ' ');
    }
 
    return 0;
}