问题分析

我们需要维护一个序列，支持单点修改和特殊查询：

查询最小的 $p$ 使得 $\text{gcd}(a_0,...,a_p) \times \text{XOR}(a_0,...,a_p) = x$

关键观察

1. 数学性质

GCD 具有单调不增性：随着前缀增长，GCD 不会增加

XOR 没有明显单调性，但可以前缀维护

2. 分块思想

由于 $n \leq 10^5$，$q \leq 10^4$，使用分块算法平衡修改和查询的复杂度。

算法思路

1. 分块设计

将序列分成大小为 $b = 320$ 的块（$\sqrt{n} \approx 316$）：

const int siz = 1e5 + 10, b = 320;

2. 块内信息维护

每个块维护：

• gc[i]: 块内所有元素的 GCD
• xo[i]: 块内前缀异或和数组
• mp[i]: 映射 异或值 -> 最小位置

void rebuild(int shu) {
    mp[shu].clear();
    int le = shu * b;
    mp[shu][a[le]] = le, gc[shu] = xo[le] = a[le];
    
    for (int i = le + 1; i < le + b; i++) {
        xo[i] = xo[i - 1] ^ a[i];
        gc[shu] = gcd(gc[shu], a[i]);
        if (!mp[shu].count(xo[i]))
            mp[shu][xo[i]] = i;
    }
}

3. 查询处理

情况1：GCD发生变化

if (__gcd(gcs, gc[i]) != gcs) {
    for (int jc = i * b; jc < min(n + 1, i * b + b); jc++) {
        gcs = gcd(gcs, a[jc]), xors ^= a[jc];
        if (xors * gcs == x) {
            ans = jc;
            break;
        }
    }
    if (ans) break;
}

当当前GCD与块GCD的GCD不等于当前GCD时，说明块内GCD会变化，需要暴力遍历。

情况2：GCD不变

else {
    if (x % gcs == 0 && mp[i].count(x / gcs ^ xors)) {
        ans = mp[i][x / gcs ^ xors];
        break;
    }
    xors ^= xo[min(n, i * b + b - 1)];
}

如果GCD不变，可以快速检查是否存在解：

检查 $x$ 是否能被当前GCD整除

检查目标异或值是否在映射表中

复杂度分析

预处理：$O(n)$ 构建分块

修改操作：$O(\sqrt{n})$ 重构单个块

查询操作：

最坏情况：$O(\sqrt{n} + \sqrt{n}) = O(\sqrt{n})$（遍历所有块 + 暴力一个块）

平均情况：$O(\sqrt{n})$ 快速跳过不变块

正确性证明

1. GCD单调性利用

由于GCD单调不增，当遇到一个块时：

如果GCD不变，可以批量处理

如果GCD变化，只需要暴力当前块

2. 映射表正确性

每个块维护从块起点开始的前缀异或值到位置的映射，保证找到最小位置。

样例解析

输入序列经过分块后：

每个块维护自己的GCD和异或信息

查询时按块顺序处理，利用GCD单调性优化

对于查询 $x$：

1.从第一个块开始，维护当前GCD和异或值

2.对于每个块，判断GCD是否变化

3.变化则暴力检查，否则快速查询映射表

4.找到第一个满足条件的位置

关键技巧

1.分块大小选择：$b = \sqrt{n}$ 平衡复杂度

2.GCD单调性：利用不变性批量处理

3.异或映射：预处理块内异或值到位置的映射

4.条件检查：$x \bmod \text{gcd} = 0$ 的必要条件

总结

本题通过分块算法高效解决了带修改的GCD-XOR查询问题：

1.分块维护：每个块独立维护GCD和异或信息

2.查询优化：利用GCD单调性减少暴力检查

3.映射加速：预处理异或值映射快速定位

4.复杂度平衡：$O(\sqrt{n})$ 的修改和查询复杂度

算法在 $n \leq 10^5$，$q \leq 10^4$ 的数据规模下高效运行。