查看原题'" class='mdui-btn mdui-btn-raised mdui-ripple'>点击加载点击跳转分块好题$\gcd$有个性质: 一旦变动则小于原来的$\frac 12$(最小的质因子为$2$)那么总共最多$\log_2 n$个不同的$\gcd$每个块记录的信息:块内前缀 gcd 块内前缀 xor 和然后对块内元素按前缀 xor 和排序修改操作: 修改对应元素,并重构元素所在块查询操作：枚举每个块,若前缀 gcd 不变,则直接在排序好的元素中二分查找否则枚举判断复杂度$O(n\sqrt n \log n)$……