E. Exquisite Array

时间限制：2 秒
内存限制：256 兆字节

问题描述

我们称一个数字数组是 $k$-exquisite 的，如果它至少包含两个元素，并且任意两个相邻元素的差的绝对值至少为 $k$。

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

排列：长度为 $n$ 的排列是一个包含从 $1$ 到 $n$ 每个整数恰好一次的数组，顺序任意。

子数组：数组的子数组是该数组中一个或多个连续元素组成的序列。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 25000$) —— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ —— 排列的长度 ($2 \le n \le 10^5$)。

每个测试用例的第二行包含 $n$ 个整数 $p_i$ —— 排列的元素 ($1 \le p_i \le n$)。保证 $p_i$ 互不相同。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $n-1$ 个整数，分别表示 $k=1, 2, \dots, n-1$ 时，$k$-exquisite 子数组的数量。

样例输入

3
5
5 1 4 2 3
3
3 2 1
4
3 1 2 4

样例输出

10 6 3 1 
3 0 
6 2 0

样例说明

第一个测试用例： $n=5, p = [5, 1, 4, 2, 3]$ - $k=1$：所有长度至少为2的子数组都是 $1$-exquisite，因为相邻元素差的绝对值至少为1（排列中任意两个不同元素差至少为1）。长度为2的子数组有4个，长度为3的有3个，长度为4的有2个，长度为5的有1个，总共 $4+3+2+1=10$ 个。 - $k=2$：需要相邻元素差的绝对值至少为2。满足条件的子数组有 $[5,1], [1,4], [4,2], [2,3], [5,1,4], [4,2,3]$，共6个。 - $k=3$：需要相邻元素差的绝对值至少为3。满足条件的子数组有 $[5,1], [5,1,4], [1,4]$，共3个。 - $k=4$：需要相邻元素差的绝对值至少为4。满足条件的子数组只有 $[5,1]$，共1个。

输出为 10 6 3 1。

第二个测试用例： $n=3, p = [3, 2, 1]$ - $k=1$：所有长度至少为2的子数组：$[3,2], [2,1], [3,2,1]$，共3个。 - $k=2$：相邻元素差的绝对值为1（不符合至少为2），因此没有满足条件的子数组，输出 0。

输出为 3 0。

第三个测试用例： $n=4, p = [3, 1, 2, 4]$ - $k=1$：所有长度至少为2的子数组共有 $3+2+1=6$ 个。 - $k=2$：满足条件的子数组有 $[3,1], [1,2], [2,4], [3,1,2]?$（检查 $|3-1|=2, |1-2|=1$ 不满足，所以不行），实际上只有 $[3,1]$ 和 $[2,4]$？再检查：$[1,2]$ 差为1，不满足。所以是 $[3,1]$ 和 $[2,4]$，以及 $[3,1,2,4]?$（中间 $|1-2|=1$ 不行）。再仔细找：可能还有 $[1,2,4]? |1-2|=1$ 不行。所以只有 $[3,1]$ 和 $[2,4]$，共2个。 - $k=3$：需要相邻元素差至少为3。子数组 $[3,1]$ 差为2，不满足；$[2,4]$ 差为2，不满足；$[3,4]$ 不存在（不连续）。因此没有满足条件的子数组，输出 0。

输出为 6 2 0。

Exquisite Array (时光倒流 / 连通性维护)

算法/并查集 #算法/时光倒流 #算法/STL #Codeforces

1. 核心思想

[!QUOTE] 核心策略：正难则反 (Time Reversal) 当题目要求随着参数变化（$k \uparrow$）不断破坏/切断结构时，通常转化为参数反向变化（$k \downarrow$），变成建设/合并结构。

• 原问题：$k$ 增大 $\rightarrow$ 满足 $|p_i - p_{i+1}| \ge k$ 的边变少 $\rightarrow$ 区间分裂 $\rightarrow$ 难维护。
• 转化后：$k$ 减小 $\rightarrow$ 满足条件的边变多 $\rightarrow$ 区间合并 $\rightarrow$ 并查集 (DSU)。

数学贡献模型： 对于一个长度为 $L$ 的连续合法区间，其贡献为 $f(L) = \frac{L(L-1)}{2}$。 当两个区间（长度 $S_a, S_b$）合并为一个新区间（长度 $S_{new}$）时，答案增量为： $$\Delta = f(S_{new}) - f(S_a) - f(S_b)$$

---

2. 算法流程 (DSU $O(N)$ 解法)

1. 预处理缝隙：遍历数组，计算相邻元素的差值 $d = |p_i - p_{i+1}|$。使用桶 (Bucket) 或邻接表 g[d] 记录差值为 $d$ 的所有下标位置。
2. 时光倒流：初始化并查集，每个点独立。从 $k = n-1$ 遍历到 $1$。
3. 动态合并：
   • 对于当前的 $k$，取出所有差值恰好为 $k$ 的相邻位置对 $(i, i+1)$。
   • 在并查集中 union(i, i+1)。
   • 根据上述公式更新全局 ans。
4. 记录答案：将当前 $k$ 的 ans 保存。

---

3. 黄金代码模板 (C++20 DSU)

// 复杂度: O(N * alpha(N)) ≈ O(N)
void solve() {
    int n; cin >> n;
    vector<int> p(n);
    for(auto& x : p) cin >> x;

    // 1. 预处理：用桶记录每种差值对应的下标位置
    // g[v] 存储所有满足 abs(p[i] - p[i+1]) == v 的下标 i
    vector<vector<int>> g(n); 
    for(int i = 0; i < n - 1; i++) {
        g[abs(p[i] - p[i+1])].push_back(i);
    }

    // 2. 并查集初始化
    vector<int> fa(n), sz(n, 1);
    iota(fa.begin(), fa.end(), 0); // fa[i] = i

    long long ans = 0;
    // 组合数公式: C(len, 2)
    auto calc = [&](long long x) { return x * (x - 1) / 2; };

    // 路径压缩查找
    function<int(int)> find = [&](int x) {
        return x == fa[x] ? x : fa[x] = find(fa[x]);
    };

    vector<long long> res(n);

    // 3. 时光倒流：从 k = n-1 到 1
    for(int k = n - 1; k >= 1; k--) {
        for(int i : g[k]) { // 将所有差值为 k 的缝隙“缝合”起来
            int x = find(i);
            int y = find(i + 1);
            if(x != y) {
                // 减去旧贡献，合并，加上新贡献
                ans -= calc(sz[x]) + calc(sz[y]); 
                sz[y] += sz[x];                   
                fa[x] = y;                        
                ans += calc(sz[y]);               
            }
        }
        res[k] = ans;
    }

    for(int k = 1; k < n; k++) cout << res[k] << " \n"[k==n-1];
}
````

---

## 4. 易错点/Debug清单 (含 Set 解法警示)

> [!WARNING] 迭代器失效陷阱 (Set 解法)
> 
> 在使用 std::set 进行正向切分时，严禁写 auto itl = p--;。
> 
> - **错误原因**：`p--` 会修改 `p` 本身的值，导致后续使用 `p` 时指向错误，且后缀操作符的返回值在复杂表达式中容易产生歧义。
>     
> - **正确写法**：使用 `std::prev(p)` 和 `std::next(p)`，它们不会修改原迭代器。
>     

> C++
> 
> ```
> auto it = st.find(val);
> auto L = prev(it); // 安全拿到前一个
> auto R = next(it); // 安全拿到后一个
> ```

> [!NOTE] 贡献计算差异
> 
> - **合并时 (DSU)**：`ans += f(A+B) - f(A) - f(B)` （整体变大，加增量）
>     
> - **分裂时 (Set)**：`ans -= A * B` （直接减去跨越切点的子数组数量，利用容斥原理优化计算，无需重算 $f$）
>     

> [!DANGER] 多测清空与溢出
> 
> 1. **全局变量**：如果在 `solve` 外定义了 `vector<int> g[N]`，必须在每轮开始用 `for` 循环手动 `clear`，且只能循环到 $n$ (不要循环到 MAXN，否则 TLE)。
>     
> 2. **整数溢出**：计算 `n * (n-1) / 2` 时，$n$ 若为 `int`，必须强转 `(long long)n`，否则 $10^5 \times 10^5$ 会爆 `int`。
>     

## 5. 参考资料

- [Codeforces 类似题: CF722C - Destroying Array](https://codeforces.com/problemset/problem/722/C) (时光倒流经典题)






# 我的AC 代码（starsilk）

> 易错点
> - 第一次算ans的时候用的 int  会爆
> - 想找到下一个位置不能直接赋值，必须 'itl--' 这种写法
> - 写完记得清空数组（好习惯）
> - 

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> d[100005];

void solve(){
    LL n;
    cin>>n;
    set<LL> st;
    vector<int> p(n);
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=1;i<n;i++){
        int v=p[i]-p[i-1];
        if(v<0) v=-v;
        d[v].push_back(i);
    }
    st.insert(0);
    st.insert(n);
    LL ans=(n-1)*n/2;
    for(int i=0;i<n-1;i++){

        for(auto it:d[i]){
            st.insert(it);
            auto p=st.find(it);
            auto itl=p,itr=p;
            itl--,itr++;

            ans-=((*itr-*p)*(*p-*itl));
        }

        cout<<ans<<" ";
    }
    cout<<endl;

    for(int i=0;i<n;i++) d[i].clear();
    return ;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}