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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| #include <bits/stdc++.h>
using namespace std;
using ld = long double;
#define int long long
#define fi first
#define se second
void solve ()
{
int n; cin >> n;
vector <int> v(n + 1), d(n + 3);
for (int i = 1; i <= n; i++) {
cin >> v[i];
d[i] = abs(v[i] - v[i - 1]);
}
vector <int> al(n + 3, 1), br(n + 3, n + 1);
vector <int> stk;
for (int i = 2; i <= n; i++) {
while (stk.size() && d[stk.back()] > d[i]) {
stk.pop_back();
}
if (stk.size()) al[i] = stk.back();
stk.push_back(i);
}
stk.clear();
for (int i = n; i >= 2; i--) {
while (stk.size() && d[stk.back()] >= d[i]) {
stk.pop_back();
}
if (stk.size()) br[i] = stk.back();
stk.push_back(i);
}
vector <int> ans(n + 1, 0);
for (int i = 2; i <= n; i++) {
ans[d[i]] += (br[i] - i) * (i - al[i]);
}
for (int i = n - 2; i >= 1; i--) {
ans[i] += ans[i + 1];
}
for (int i = 1; i < n; i++) {
cout << ans[i] << " \n"[i == n - 1];
}
}
signed main ()
{
ios::sync_with_stdio(0);
cin.tie(0);
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
|
