#PQJ2747x16454. QOJ 2747_16454

    ID: 2861 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:HEOI 2015数学线段树平衡树

QOJ 2747_16454

公约数数列 【题目细节】 gcdxor.cpp/.c/.pas/.in/.out 时间限制:1s 空间限制:256M

【问题描述】 设计一个数据结构. 给定一个正整数数列 a_0, a_1, ..., a_{n - 1},你需要支持以下两种操 作:

  1. MODIFY id x: 将 a_{id} 修改为 x.
  2. QUERY x: 求最小的整数 p (0 <= p < n),使得 gcd(a_0, a_1, ..., a_p) * XOR(a_0, a_1, ..., a_p) = x. 其中 XOR(a_0, a_1, ..., a_p) 代表 a_0, a_1, ..., a_p 的异或和,gcd 表示最大公约数。

【输入格式】 从gcdxor.in 中读入。 输入数据的第一行包含一个正整数 n. 接下来一行包含 n 个正整数 a_0, a_1, ..., a_{n - 1}. 之后一行包含一个正整数 q,表示询问的个数。 之后 q 行,每行包含一个询问。格式如题目中所述。

【输出格式】 输出到gcdxor.out 中 对于每个 QUERY 询问,在单独的一行中输出结果。如果不存在这样的 p,输出 no.

【样例输入】 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% 的数据,n <= 10000,q <= 1000. 对于 100% 的数据,n <= 100000,q <= 10000,a_i <= 10^9 (0 <= i < n),QUERY x 中的 x <= 10^18,MODIFY id x 中的 0 <= id < n,1 <= x <= 10^9.