BZOJ 4028: [HEOI2015]公约数数列【分块 + 前缀GCD】

任意门：https://www.lydsy.com/JudgeOnline/problem.php?id=4028

4028: [HEOI2015]公约数数列

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 1177 Solved: 456
[Submit][Status][Discuss]

Description

设计一个数据结构. 给定一个正整数数列 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表示最大公约数。

Input

输入数据的第一行包含一个正整数 n.

接下来一行包含 n 个正整数 a_0, a_1, ..., a_{n - 1}.

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

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

Output

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

Sample Input

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

Sample Output

6
0
no
2
8
8

HINT

对于 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.

解题思路：

暴力出奇迹。

这种蜜汁区间查询的考虑莫队或者分块。

当然这里是分块啦，在线动态更新嘛。

每一块维护的信息有：

①：Xor[ i ] 位置 i 到它所在块的最左端的异或前缀和。

②：Gcd[ i ] 位置 i 到它所在块的最左端的前缀GCD。

为什么这样维护前缀GCD呢？因为区间【1~N】的前缀GCD 肯定是递减的，，而且每次减小最少都是除以2，那么GCD的种类最多也是logN。

由于前缀GCD是递减的，那么如果加上一块的数据后GCD不变，那就说明这一块里所有数的前缀GCD都是不变的。

那么暴力寻解的时候我们分两类情况讨论：

一类是加上这块后 GCD不变，那么只要查询这一块里面有没有符合条件的异或前缀和即可，（这里预处理时 hash 一下，代码用了stl里的set），查询时直接查这一块的 hash 表即可。

一类是加上这一块后GCD改变的，暴力枚举啦 logN

AC code：

 1 #include <bits/stdc++.h>
 2 #define LL long long
 3 using namespace std;
 4 const int MAXN = 1e5+10;
 5 int N, M;
 6 int bl[1001], br[1001], pos[MAXN], block, num;
 7 int Gcd[MAXN], Xor[MAXN];
 8 int a[MAXN];
 9 set<int>S[1001];
10 int gcd(int a, int b) {return b==0?a:gcd(b, a%b);}
11 void build(int t)
12 {
13     S[t].clear();
14     Gcd[bl[t]] = a[bl[t]]; Xor[bl[t]] = a[bl[t]];
15     S[t].insert(Xor[bl[t]]);
16     for(int i = bl[t]+1; i <= br[t]; i++){
17         Gcd[i] = gcd(Gcd[i-1], a[i]);
18         Xor[i] = Xor[i-1]^a[i];
19         S[t].insert(Xor[i]);
20     }
21 }
22 
23 int main()
24 {
25     int id, val;
26     scanf("%d", &N);
27     for(int i = 1; i <= N; i++){
28         scanf("%d", &a[i]);
29     }
30 
31     block = (int)sqrt(N);
32     for(int i = 1; i <= N; i+=block){
33         bl[++num] = i; br[num] = min(N,i+block-1);
34         for(int j = bl[num]; j <= br[num]; j++)
35             pos[j] = num;
36     }
37 
38     for(int i = 1; i <= num; i++) build(i);
39 
40     char com[10];
41     scanf("%d", &M);
42     while(M--){
43         scanf("%s", com);
44         if(com[0] == 'M'){
45             scanf("%d %d", &id, &val);
46             a[++id] = val;
47             build(pos[id]);
48         }
49         else{
50             LL xx = 0;
51             int Lxor = 0, Lgcd = 0;
52             scanf("%lld", &xx);
53             int flag = 0;
54             for(int i = 1; i <= num; i++){
55                 int T = gcd(Lgcd, Gcd[br[i]]);
56                 if(T != Lgcd){
57                     for(int j = bl[i]; j <= br[i]; j++)
58                         if((LL)gcd(Lgcd, Gcd[j])*(LL)(Xor[j]^Lxor) == xx){
59                             flag = j;
60                             break;
61                         }
62                     if(flag) break;
63                 }
64                 else{
65                     if(xx%T == 0 && S[i].count((int)(xx/T)^Lxor)){
66                         for(int j = bl[i]; j <= br[i]; j++){
67                             if((LL)gcd(Lgcd, Gcd[j])*(LL)(Xor[j]^Lxor) == xx){
68                                 flag = j;
69                                 break;
70                             }
71                         }
72                     }
73                     if(flag) break;
74                 }
75                 Lgcd = T; Lxor^=Xor[br[i]];
76             }
77             if(flag == 0) puts("no");
78             else printf("%d
", flag-1);
79         }
80     }
81     return 0;
82 }