Codeforces Round 1072 (Div.3) E题题解#

题意：#

定义精致数组- $k$ 为任意相邻两数之差至少为 $k$ 的数组。

给定长度为 $n$ 的排列 $p$ ，对于每一个从 $1$ 到 $n - 1$ 的 $k$ ，找出精致数组- $k$ 的数量。

思路：#

题目要求: 寻找相邻差值至少为 $k$ 的数组个数。

这可以转化为：寻找差分数组中某一子段的最小值至少为 $k$ 的数组个数。

这仍然很麻烦。于是我们可以先统计出最小值为 $k,k\in [1, n - 1]$ 的子段数，最后再做前缀和即可转换为最小值至少为 $k$ 的数组个数。

关于统计最小值为 $k$ 的子段数，我们可以对差分数组中的每一个数进行单独计算：

对于第 $i$ 个差值，我们可以利用两次单调栈统计出第 $i$ 个差值左侧最近的满足 $d[l]<=d[i]$ 的 $l$ 和右侧最近的满足 $d[r]<d[i]$ 的 $r$ ，这样即可以求出对于当前的 $d[i]$ ，以 $d[i]$ 为最小值的数组个数： $(i - l + 1 - 1) \times (r - i + 1 - 1)$ ，即： $(i - l) \times (r - i)$ 。

这样即可不重不漏地统计出所有最小值为 $k$ 的子段数，最后再从 $1$ 到 $n$ 做前缀和即可求出最小值至少为 $k$ 的数组个数。

代码：#

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ld = long double;
4
#define int long long
5
#define fi first
6
#define se second
7

8
void solve ()
9
{
10
    int n; cin >> n;
11
    vector <int> v(n + 1), d(n + 3);
12
    for (int i = 1; i <= n; i++) {
13
        cin >> v[i];
14
        d[i] = abs(v[i] - v[i - 1]);
15
    }
16

17
    vector <int> al(n + 3, 1), br(n + 3, n + 1);
18
    vector <int> stk;
19

20
    for (int i = 2; i <= n; i++) {
21
        while (stk.size() && d[stk.back()] > d[i]) {
22
            stk.pop_back();
23
        }
24
        if (stk.size()) al[i] = stk.back();
25
        stk.push_back(i);
26
    }
27

28
    stk.clear();
29
    for (int i = n; i >= 2; i--) {
30
        while (stk.size() && d[stk.back()] >= d[i]) {
31
            stk.pop_back();
32
        }
33
        if (stk.size()) br[i] = stk.back();
34
        stk.push_back(i);
35
    }
36

37
    vector <int> ans(n + 1, 0);
38
    for (int i = 2; i <= n; i++) {
39
        ans[d[i]] += (br[i] - i) * (i - al[i]);
40
    }
41

42
    for (int i = n - 2; i >= 1; i--) {
43
        ans[i] += ans[i + 1];
44
    }
45

46
    for (int i = 1; i < n; i++) {
47
        cout << ans[i] << " \n"[i == n - 1];
48
    }
49
}
50

51
signed main ()
52
{
53
    ios::sync_with_stdio(0);
54
    cin.tie(0);
55
    int _ = 1;
56
    cin >> _;
57
    while (_--) {
58
        solve();
59
    }
60
    return 0;
61
}