题解：CF2184E Exquisite Array

小屹0_0 · 2026-04-20 15:07:30 · 题解

套路题吧。

考虑求出所有相邻两项的差，再从小到大统计每一个 k 精致数组的个数。

我们考虑将每一个差和每一个差对应的下标（即如果当前的差是 | a_i - a_{i + 1} |，那么下标记为 i）用一个二元组 (num, id) 表示。

然后把他们按照 num 从小到大排序。

我们要统计差大于等于 k，等价于统计最小值等于 k 然后求一个后缀和即可。

这个过程中我们考虑从小到大算答案，设 f(x) 为差的最小值是 x 的个数，当前枚举到的差是 (num, id)。

那么设之前已经考虑过的所有的二元组中 id 比当前 id 小的最大的，记为 dn，同理，找到比 id 大的最小的，记为 up。

那么我们就可以直接 f(num) \leftarrow f(num) + (up - id) \cdot (id - dn)。

注意一下特殊情况，也就是有多个差相同，此时分类讨论，发现我们上面的式子可以直接做，不会出现问题。

然后前缀的前驱后继可以直接用 set 做。

code

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

#define int long long
const int N = 1e5 + 5;

int n, a[N], c[N], ans[N];

struct node
{
    int x, id;
    bool operator<(const node &t)
    {
        return (x == t.x ? id < t.id : x < t.x);
    }
} d[N];

void please_ac()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        ans[i] = 0;
    }
    for (int i = 1; i < n; i++)
        c[i] = abs(a[i + 1] - a[i]), d[i] = {c[i], i};

    sort(d + 1, d + n);

    set<int> s;
    s.insert(0), s.insert(n);

    for (int i = 1; i < n; i++)
    {
        int up = *s.lower_bound(d[i].id);
        int dn = *prev(s.lower_bound(d[i].id));
        ans[d[i].x] += (up - d[i].id) * (d[i].id - dn);
        s.insert(d[i].id);
    }

    for (int i = n - 1; i >= 1; i--)
        ans[i] += ans[i + 1];

    for (int i = 1; i < n; i++)
        cout << ans[i] << " ";
    cout << "\n";
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T_T = 1;
    cin >> T_T;
    while (T_T--)
        please_ac();
}