F. Good Pairs 详细题解（附标程解析）

一、题目核心理解

给定数组 $a$（长度为 $n$）和整数 $k$，定义好数对 $(l,r)$： 存在递增下标序列 $i_1=l,i_2,\dots,i_m=r$，满足相邻元素的绝对差 $|a_{i_j}-a_{i_{j+1}}| \le k$。 要求统计所有满足 $1 \le l \le r \le n$ 的好数对数量。

关键转化

1. 单个元素 $(i,i)$ 一定是好数对，共 $n$ 个；
2. 核心难点：统计满足条件的 $l<r$ 的好数对。

---

二、核心算法思路（官方标程解法）

1. 问题等价转化

数对 $(l,r)$ 是好数对 $\iff$ 从 $l$ 出发，能通过向右跳跃（下标递增）到达 $r$，且每次跳跃的元素值差 $\le k$。

标程采用逆向思维 + 数据结构优化，分三部分计算答案：

$$\text{总答案} = \text{相同元素对数量} + \text{正向合法数对} + \text{逆向合法数对} $$

2. 核心定义

• 相同元素对：所有 $l \le r$ 且 $a_l=a_r$ 的数对（这类数对天然满足 $|a_l-a_r|=0 \le k$）；
• 正向合法数对：从左到右，满足条件的 $l<r$；
• 逆向合法数对：将数组反转后，统计的合法数对（补全所有场景）。

3. 数据结构作用（标程核心）

1. 线段树（ST）：维护值区间内最靠左的下标，快速查询 $[a_i+1, a_i+k]$ 范围内最小的下标 $j$；
2. 树状数组（FenwickTree）：维护值的出现次数，快速查询区间元素数量；
3. dp数组：$dp[i]$ 表示以 $i$ 为起点，向右能形成的新合法数对数量。

---

三、标程逐部分解析

1. 全局常量与数据结构

const ll MAX=1000100;  // 元素最大值上限（a_i ≤ 1e5）
// 线段树：维护值区间的最小下标（找最左可达位置）
class ST{...}  
// 树状数组：维护值的频率（区间求和）
struct FenwickTree{...}

FenwickTree freq(MAX);  // 全局树状数组：统计值出现次数
ST segtree(MAX);        // 全局线段树：查询最小下标
vector<ll> dp(MAX,0);   // dp数组：记录以i为起点的合法数对数量

2. 核心求解函数 solve

功能：统计数组中从左向右跳跃的合法数对数量（$l<r$）。 执行逻辑：从右向左遍历数组（倒序处理）

1. 对当前元素 $a[i]$，查询值范围 $[a[i]+1, a[i]+k]$ 内最小的下标 $j$（最左的可达位置）；
2. 状态转移：
   • 若 $j$ 有效：$dp[i] = dp[j] +$ 区间 $[a[i]+1,a[j]]$ 的元素个数；
   • 若 $j$ 无效：$dp[i] = 0$；
3. 累加所有 $dp[i]$，得到正向合法数对；
4. 清空数据结构，为下一组测试用例做准备。

ll solve(vector<ll> a,ll n,ll k){
    ll now=0;
    for(ll i=n-1;i>=0;i--){  // 倒序遍历
        // 查询 [a[i]+1, a[i]+k] 最小下标j
        ll j=segtree.query(a[i]+1,a[i]+k);
        // dp转移方程
        if(j<n) dp[i]=dp[j]+freq.sum(a[i]+1,a[j]);
        else dp[i]=0;
        now+=dp[i];  // 累加总合法数对
        // 更新数据结构：记录a[i]的下标i
        segtree.upd(a[i],i);
        freq.add(a[i],1);
    }  
    // 清空全局数据结构
    for(auto it:a){  
        segtree.upd(it,MAX);  
        freq.add(it,-1); 
    }
    return now;
}

3. 主函数 solve（测试用例处理）

总答案计算逻辑：

1. 统计相同元素对（天然合法）；
2. 调用 solve 统计正向合法数对；
3. 反转数组，调用 solve 统计逆向合法数对；
4. 三者相加即为最终答案。

void solve(){         
    ll n,k; cin>>n>>k;
    vector<ll> a(n);
    ll ans=0;
    map<ll,ll> cnt;  
    // 统计相同元素对数量
    for(auto &it:a){
        cin>>it;
        cnt[it]++;
        ans+=cnt[it];
    }
    ans+=solve(a,n,k);      // 正向合法数对
    reverse(a.begin(),a.end()); 
    ans+=solve(a,n,k);      // 逆向合法数对
    cout<<ans<<"\n"; 
} 

---

四、时间复杂度分析

• 线段树/树状数组的单次操作：$O(\log \text{MAX})$；
• 数组遍历：$O(n)$；
• 总复杂度：$O(n \log \text{MAX})$；
• 完全适配题目约束：$n \le 5 \times 10^5$，多组测试用例总和不超限。

---

五、样例验证（第一个样例）

输入：

3 0
1 1 1

1. 相同元素对：$(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)$ → 数量 $6$；
2. 正向+逆向合法数对：$0$；
3. 总答案：$6$，与样例输出一致。

第二个样例输出 $9$，也完全匹配标程计算逻辑。

---

六、总结

核心考点

1. 问题转化：将路径可达问题转化为值区间跳跃问题；
2. 动态规划：用 $dp[i]$ 快速统计以 $i$ 为起点的合法数对；
3. 数据结构优化：线段树+树状数组解决区间查询、单点更新，保证效率；
4. 正逆向遍历：补全所有合法数对场景。

标程亮点

• 全局复用数据结构，减少内存开销；
• 倒序遍历+DP转移，完美适配跳跃逻辑；
• 分三部分计算答案，逻辑清晰、效率拉满。