CF-1072-E. Exquisite Array · znzryb
## 题目大意
给定一个长度为 n 的排列 p。定义一个数组为 k-exquisite 当且仅当：
- 该数组至少包含两个元素
- 任意两个相邻元素的差的绝对值至少为 k
对于每个 k（从 1 到 n-1），需要求出排列 p 中有多少个子数组是 k-exquisite 的。
**输入格式：**
- 第一行：测试用例数 t（1 ≤ t ≤ 25000）
- 每个测试用例：
- 第一行：整数 n，排列的长度（2 ≤ n ≤ 10⁵）
- 第二行：n 个整数 p₁, p₂, ..., pₙ，表示排列（1 ≤ pᵢ ≤ n，且各不相同）
**输出格式：**
对于每个测试用例，输出 n-1 个整数，**第 i 个整数表示 i-exquisite 子数组的个数。**
**数据范围：**
- 时间限制：2 秒
- 内存限制：256 MB
- 所有测试用例的 n 之和不超过 2×10⁵
## 思路讲解
~~感觉比 D，B 简单。~~
如果只需要求这个 k-exquisite 子数组的个数，那就直接双指针，不过这波是要求这个 i-exquisite 子数组的个数。
我们想到，其实这个无非就是把整个数组切成了几段，我们可以采用***做减法***的方式，去解决这个问题。具体来讲，设我们所求的这个子数组参数为 $k$，一个差值 $\Delta$，$k≤\Delta$ 可以直接跨过去，$k>\Delta$ 就不可以。
不难想到，我们可以对这个差值进行排序，或者一种更方便的实现是使用这个 map，并在 set 中存放分隔点，初始设置为这个 0，N（其实这里是一个坑点，不要选成 0，N+1 了，因为我们的分隔点采用前向点，最大为 N-1，因此哨兵应该选 N）。不难发现，设我们的新分隔点为 $pos$，set 数组中第一个比我们小的数字是 $low$，第一个比我们大的数字是 $high$，我们所需要减去的值就是 $(pos-low)\times(high-pos)$，即 low 区有 $(pos-low)$ 种选择，high 区是 $(high-pos)$ 种选择，使用乘法原理乘起来即可。
```cpp
set<ll> st={0,N};
for (int i=1;i<=N-1;++i) {
cout<<ans<<" ";
for (auto pos:mp_diff_pos[i]) {
ll low=get_lower(pos);
ll high=*st.lower_bound(pos);
ll minus=(pos-low)*(high-pos);
ans-=minus;
st.insert(pos);
}
}
```
## AC代码
AC
[https://codeforces.com/contest/2184/submission/357897043](https://codeforces.com/contest/2184/submission/357897043)
::: 源代码
```cpp
/**
* Problem: E. Exquisite Array
* Contest: Codeforces Round 1072 (Div. 3)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2184/problem/E
* Created: 2026-01-14 17:56:05
* Author: Gospel_rock
*/
#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT;
/*
*
*/
// struct pos_diff {
// ll pos;
// ll diff;
// pos_diff(ll p,ll d):pos(p),diff(d) {
//
// }
// bool operator<(const pos_diff &o) const {
// if (diff!=o.diff) return diff<o.diff;
// return pos<o.pos;
// }
// };
void Solve() {
ll N;
cin >> N;
vector<ll> P(N);
for (int i=0;i<N;++i) {
cin>>P[i];
}
// deque<pos_diff> vec_pos_diff;
map<ll,vector<ll>> mp_diff_pos;
for (int i=0;i<N-1;++i) {
ll diff=abs(P[i]-P[i+1]);
mp_diff_pos[diff].push_back(i+1);
}
ll ans=N*(N-1)/2;
set<ll> st={0,N};
auto get_lower=[&](ll x) {
auto it=st.lower_bound(x);
--it;
return *it;
};
for (int i=1;i<=N-1;++i) {
cout<<ans<<" ";
// if (mp_diff_pos[i].empty()) {
// continue;
// }
for (auto pos:mp_diff_pos[i]) {
ll low=get_lower(pos);
ll high=*st.lower_bound(pos);
ll minus=(pos-low)*(high-pos);
ans-=minus;
st.insert(pos);
}
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> lT;
while(lT--)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2184/submission/357897043
*/
```
:::
## 心路历程（WA，TLE，MLE……）