CF2184E

可以把它看成一个区间合并问题，一开始所有区间的长度为 1，个数为n，此时每个区间是符合“n”优美数组的。

然后把相邻之差绝对值为 n - 1 的两个区间合并，现在所有的区间都满足 “n - 1” 优美数组。

如果一个区间长度为 x，它是一个优美区间，那么它一共有多少个优美子区间？

长度从 2~x，从x - 1加到1，总共是 $\frac{x(x-1)}{2}$ 个优美子区间

以此类推，i 从 n 到 1 枚举，每次合并相差为 i 的区间，计算对答案的贡献。

可以维护所有区间的总和。每次合并时，用总贡献，减去合并的两个区间的贡献，再加上新合并区间的贡献就可以了。

维护区间合并可以使用并查集。

最多合并 n - 1 次，复杂度：$O(n * f(n))$，其中 $f(n)$ 是合并区间的复杂度。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
using pii = pair<int, int>;
struct DSU {
  vector<int> pa, sz;
  void init(int n) {
    pa.resize(n + 1), sz.assign(n + 1, 1);
    iota(pa.begin(), pa.end(), 0);
  }
  int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (sz[x] < sz[y]) swap(x, y);
    pa[y] = x;
    sz[x] += sz[y];
  }
  int get(int x) { return sz[find(x)]; }
} dsu;
ll calc(ll x) { return x * (x - 1) / 2; }

void solve() {
  int n;
  cin >> n;
  dsu.init(n);
  vector<int> a(n);
  vector<vector<pii>> mar(n);
  vector<ll> ans(n, 0);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n - 1; i++) {
    mar[abs(a[i + 1] - a[i])].emplace_back(i, i + 1);
  }
  ll sum = 0;
  for (int i = n - 1; i; i--) {
    for (auto [x, y] : mar[i]) {
      x = dsu.find(x), y = dsu.find(y);
      int szx = dsu.get(x), szy = dsu.get(y);
      dsu.unite(x, y);
      sum = sum - calc(szx) - calc(szy) + calc(szx + szy);
    }
    ans[i] = sum;
  }
  for (int i = 1; i < n; i++) cout << ans[i] << ' ';
  cout << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}