C. Eri 与扩展集合 详细题解

问题重述

给定一个数组 $a$，定义子数组 $[l, r]$ 是精彩的，如果将其中的元素放入集合后，可以通过有限次操作（选择两个不同元素 $x, y$，若 $\frac{x+y}{2}$ 是正整数且不在集合中，则加入它）使集合变成连续的（即排序后相邻元素差为 $1$）。统计精彩子数组的数量。

关键观察

观察 1：最终集合的性质

设最终连续集合为 $c_1, c_2, \dots, c_m$（已排序）。定义差分数组：

$$b_i = c_{i+1} - c_i$$

性质 1：每个 $b_i$ 必须是奇数。

证明：如果某个 $b_i$ 是偶数，设 $b_i = 2k$，则 $c_{i+1} = c_i + 2k$。那么 $\frac{c_i + c_{i+1}}{2} = c_i + k$ 是正整数且介于两者之间。由于最终集合是连续的，这个数必须已经在集合中，矛盾。因此 $b_i$ 不能是偶数。

性质 2：相邻的 $b_i$ 不能不同。

证明：假设 $b_i \neq b_{i+1}$，且两者都是奇数。则：

$$c_{i+2} - c_i = b_i + b_{i+1}$$

这是偶数。那么 $\frac{c_i + c_{i+2}}{2}$ 是整数，且不等于 $c_{i+1}$（因为 $b_i \neq b_{i+1}$），这个数应该存在于连续集合中，矛盾。

结论：所有 $b_i$ 相等且为奇数。因此最终集合是一个公差为奇数的等差数列。

观察 2：操作的本质

操作相当于在集合中插入两个数的中点。这类似于在数轴上不断取中点填充空隙。实际上，给定初始集合，能生成的数集是初始数的所有整数线性组合：

$$\{ \sum \lambda_i a_i \mid \lambda_i \in \mathbb{Z}, \sum \lambda_i = 1 \} $$

更具体地说，最终能得到的连续集合的公差等于初始集合中所有数差的最大奇因子。

设 $g = \gcd\{a_i - a_j \mid i \neq j\}$，则：

• 最终公差 $d$ 是 $g$ 的奇数部分，即 $g$ 除以 $2$ 的幂次后的结果
• 最终集合能成为连续集合当且仅当 $g$ 是 $2$ 的幂次

因此：子数组 $[l, r]$ 是精彩的当且仅当其中所有数的差的最大公约数是 $2$ 的幂次。

观察 3：差分数组的处理

设 $d_i = |a_{i+1} - a_i|$（$1 \le i < n$）。对于子数组 $[l, r]$，考虑其内部差分的最大公约数：

$$g_{l,r} = \gcd\{d_l, d_{l+1}, \dots, d_{r-1}\}$$

则 $[l, r]$ 是精彩的当且仅当 $g_{l,r}$ 是 $2$ 的幂次。

注意：当子数组只有一个元素时，差分集合为空，规定 $g = 0$，此时是精彩的（单个元素集合总是连续的）。

观察 4：单调性与双指针

对于固定的左端点 $l$，随着 $r$ 增大，$g_{l,r}$ 是单调不增的（因为取更多数的 $\gcd$ 只会减小或不变）。因此，满足 $g_{l,r}$ 是 $2$ 的幂次的最大 $r$ 可以通过双指针找到。

算法步骤

1. 预处理差分：计算 $d_i = |a_{i+1} - a_i|$，长度为 $n-1$

2. 处理相同元素：如果 $d_i = 0$，意味着相邻元素相等。这些位置需要特殊处理，因为 $0$ 的 $\gcd$ 仍为 $0$（被认为是 $2$ 的幂次）

3. 双指针维护：

   • 使用两个指针 $l$ 和 $r$ 遍历差分数组
   • 维护当前区间内所有 $d$ 的 $\gcd$
   • 当 $\gcd$ 的二进制表示中 $1$ 的个数 $\le 1$（即 $2$ 的幂次）时，$r$ 可以右移
   • 否则需要移动左指针

4. 计数答案：

   • 对于每个左端点，找到满足条件的最右 $r$
   • 统计所有子数组数量

时间复杂度

• 预处理：$O(n)$
• 双指针：每个元素入队出队一次，$O(n)$
• 总复杂度：$O(n)$（$\gcd$ 操作视为 $O(1)$）

完整代码

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define REP(i,b,e) for(int i=(b);i<(int)(e);++i)

int n;
int a[400005], lsteq[400005];

// 双指针结构体
struct two_pointers {
    int l, r, mid;
    int val[400005], rt;
    
    void init() {
        l = r = mid = rt = 0;
        val[0] = a[0];
    }
    
    // 右指针右移
    inline void addr() {
        ++r;
        rt = __gcd(rt, a[r]);
    }
    
    // 左指针右移
    inline void addl() {
        if (l + 1 > r) addr();
        ++l;
        if (l > mid) {
            rt = 0;
            mid = r;
            val[mid] = a[mid];
            for (int i = mid - 1; i >= l; --i) {
                val[i] = __gcd(val[i + 1], a[i]);
            }
        }
    }
    
    // 查询当前区间 [l, r] 的 gcd
    inline int query() {
        return __gcd(val[l], rt);
    }
};

// 判断 x 是否是 2 的幂次
bool is_power_of_two(int x) {
    if (x == 0) return true;  // 0 被认为是 2^? 的特殊情况
    return (x & (x - 1)) == 0;
}

void Main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    // 计算差分数组
    for (int i = 1; i < n; i++) {
        a[n - i] -= a[n - i - 1];
    }
    for (int i = 1; i < n; i++) {
        a[i - 1] = llabs(a[i]);
    }
    --n;  // 差分数组长度为 n-1
    
    // 预处理下一个非零位置
    lsteq[n] = n;
    for (int i = n - 1; i >= 0; --i) {
        lsteq[i] = (a[i] ? i : lsteq[i + 1]);
    }
    
    two_pointers p;
    p.init();
    
    long long ans = 1;  // 单个元素的子数组
    int cnt = 1;
    
    for (int i = 0; i < n; i++) {
        if (lsteq[i] == i) {  // 当前差分非零
            while (p.l < i) p.addl();
            // 扩展右指针直到 gcd 不是 2 的幂次
            while (p.r < n && is_power_of_two(p.query())) {
                p.addr();
            }
            ans += (n - p.r) * cnt + 1;
            cnt = 1;
        } else {
            // 当前差分为零，可以合并
            ans += lsteq[i] - i + 1;
            ++cnt;
        }
    }
    
    cout << ans << "\n";
}

void TC() {
    int tc = 1;
    cin >> tc;
    while (tc--) {
        Main();
        cout.flush();
    }
}

signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    TC();
    return 0;
}

代码说明

1. 差分计算：$a_i' = |a_{i+1} - a_i|$

2. 相同元素处理：当 $d_i = 0$ 时，相邻元素相等，这些位置可以"合并"处理

3. 双指针维护：

   • val[l] 存储从 $l$ 到 mid 的 $\gcd$
   • rt 存储从 mid+1 到 $r$ 的 $\gcd$
   • 整体 $\gcd = \gcd(val[l], rt)$

4. 判断 $2$ 的幂次：(x & (x-1)) == 0 且 $x > 0$，$0$ 特殊处理

5. 计数：

   • 对于每个差分非零位置，找到能延伸的最大右端点
   • 对于连续零的位置，一起处理

示例验证

以第二个测试用例 [1,3,6,10,15,21] 为例：

• 差分：$[2,3,4,5,6]$
• 检查子数组：
  • $[1,3]$：差 $2$，是 $2$ 的幂次 ✓
  • $[3,6,10]$：差 $3,4$，$\gcd=1$，是 $2$ 的幂次 ✓
  • 等等

最终答案 $18$ 与示例一致。

总结

本题的核心技巧：

1. 将集合能否变成连续集合转化为差分的 $\gcd$ 是否为 $2$ 的幂次
2. 利用 $\gcd$ 的单调性使用双指针
3. 处理相同元素时的合并技巧
4. $O(n)$ 时间解决