#P4028. [HEOI2015]公约数数列

    ID: 3229 传统题 1000ms 256MiB 尝试: 1274 已通过: 324 难度: 8 上传者: 标签>CF2400提高+/省选-区间 GCD 状态压缩普通线段树线段树上二分异或抵消根号分块整块懒标记哈希表

[HEOI2015]公约数数列

题目描述

设计一个数据结构. 给定一个正整数数列 a0,a1,...,an−1a_0, a_1, ..., a_{n - 1},你需要支持以下两种操作:

  1. MODIFY id x: 将 aida_{id} 修改为 xx。
  2. QUERY x: 求最小的整数 p(0≤p<n)p (0 \le p < n),使得 $gcd(a_0, a_1, ..., a_p) \times xor(a_0, a_1, ..., a_p) =x$。其中 xor(a0,a1,...,ap)xor(a_0, a_1, ..., a_p) 代表 a0,a1,⋯ ,apa_0, a_1, \cdots, a_p 的异或和,gcdgcd 表示最大公约数。

输入格式

输入数据的第一行包含一个正整数 nn。

接下来一行包含 nn 个正整数 a0,a1,...,an−1a_0, a_1, ..., a_{n - 1}。

之后一行包含一个正整数 qq,表示询问的个数。

之后 qq 行,每行包含一个询问。格式如题目中所述。

输出格式

对于每个 QUERY 询问,在单独的一行中输出结果。如果不存在这样的 pp,输出 nono.

10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
MODIFY 7 20321280
QUERY 162343680
QUERY 1832232960000
MODIFY 0 92160
QUERY 1234567
QUERY 3989856000
QUERY 833018560
MODIFY 3 8600
MODIFY 5 5306112
QUERY 148900352
6
0
no
2
8
8

数据范围

对于 30%30\% 的数据,n≤104n \le 10^4,q≤103q \le 10^3。

对于 100%100\% 的数据,n≤105n \le 10^5,q≤104q \le 10^4,ai≤109(0≤i<n)a_i \le 10^9 (0 \le i < n),QUERY x 中的 x≤1018x \le 10^{18},MODIFY id x 中的 0≤id<n0 \le id < n,1≤x≤1091 \le x \le 10^9。