「HEOI2015」公约数数列

发表于
字数统计: 1,174字 | 阅读时长 ≈ 6min

「HEOI2015」公约数数列

题目描述

设计一个数据结构. 给定一个正整数数列 $a_0, a_1, \ldots , a_{n - 1}$，你需要支持以下两种操作：

  1. MODIFY id x: 将 $a_{\text{id}}$ 修改为 $x$.
  2. QUERY x: 求最小的整数 $p$ ($0 \leq p < n$)，使得 $\text{gcd}(a_0, a_1, …, a_p) \cdot \text{XOR}(a_0, a_1, …, a_p) = x$. 其中 $\text{XOR}(a_0, a_1, …, a_p)$ 代表 $a_0, a_1, \ldots , a_p$ 的异或和，$\text{gcd}$ 表示最大公约数。
输入格式

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

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

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

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

输出格式

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

数据范围与提示

对于 $100\%$ 的数据，$n \leq 100000, \ q \leq 10000, \ a_i \leq 10^9 (0 \leq i < n)$，QUERY x 中的 $x \leq 10^{18}$，MODIFY id x 中的 $0 \leq \text{id} < n, \ 1 \leq x \leq 10^9$。

首先觉得直接上数据结构很不好维护，多半是分块。

这道题由于是前缀$gcd$，所以不同的$gcd$是$O(loga_0)$的（将$a_0$标准分解后考虑不难得知）。这提示我们可以枚举每个前缀$gcd$，在对应区间里查找是否有$x/gcd$的异或前缀和。如果没有修改操作，主席树可以轻松解决。有了修改操作就不那么好做了，下面考虑分块。

维护异或前缀和$sxor$。每个块里记录：块内所有数的$gcd$:$sgcd$，块的左右端点处的前缀$gcd$:$st,en$（整个$0$~$n-1$的区间），整体修改标记$lazy$，以及用unordered_map实现的Hash表，用于记录块内每个数的出现位置。

对于修改操作：异或前缀和部分，块内的$sxor$暴力修改，同时更新Hash表，之后整块修改$lazy$标记。$gcd$部分，通过暴力遍历得到整个块的$sgcd$，之后更新整块的$st$和$en$。

对于询问操作：按照块的左右顺序讨论。如果两块的左端点$st$值相等，那么说明这一块的前缀$gcd$都相等，此时直接在块里的Hash表查；否则暴力遍历查找。注意第一个判定是必要的——前面说明了不同的$gcd$只有$O(loga_0)$个，这里保证了询问操作的复杂度。

如果把求$gcd$和Hash表的复杂度视为常数，那么修改操作是$O(\sqrt n)$的，询问操作是$O(\sqrt nlogn)$的，可以通过本题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#define ll long long
#define MAXN 200005
#define MAXB 666
using namespace std;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

int N,Q;ll A[MAXN];
int cntb,be[MAXN],l[MAXB],r[MAXB];
ll sgcd[MAXB],lazy[MAXB],sxor[MAXN],st[MAXB],en[MAXB];
unordered_map<ll,int>pos[MAXB];

void Init(){
	int i,j,s;
	ll tmp=0;
	s=sqrt(N);
	for(i=j=1;i<=N;i++){
		be[i]=j;
		if(i%s==0)r[j]=i,l[++j]=i+1;
	}
	r[j]=N;l[1]=1;cntb=j;
	for(i=1;i<=cntb;i++){
		st[i]=gcd(en[i-1],A[l[i]]);
		for(j=l[i];j<=r[i];j++)sgcd[i]=gcd(sgcd[i],A[j]);
		en[i]=gcd(en[i-1],sgcd[i]);
	}
	for(i=1;i<=N;i++)sxor[i]=sxor[i-1]^A[i];
	for(i=N;i;i--)pos[be[i]][sxor[i]]=i;
}

void Modify(int id,ll x){
	int i,p=be[id];
	ll tmp=A[id]^x;
	A[id]=x;
	
	pos[p].clear();
	for(i=id;i<=r[p];i++)sxor[i]^=tmp;
	for(i=p+1;i<=cntb;i++)lazy[i]^=tmp;
	for(i=r[p];i>=l[p];i--)pos[p][sxor[i]]=i;
	
	for(sgcd[p]=0,i=l[p];i<=r[p];i++)sgcd[p]=gcd(sgcd[p],A[i]);
	for(i=p;i<=cntb;i++){
		st[i]=gcd(A[l[i]],en[i-1]);
		en[i]=gcd(en[i-1],sgcd[i]);
	}
}

void Query(ll x){
	int i,j,p,ret;
	ll tmp,las=0;
	for(i=1;i<=cntb;i++){
		if(st[i]==st[i+1]){
			if(x%st[i]==0){
				tmp=x/st[i];
				ret=pos[i][tmp^lazy[i]];
				if(ret){printf("%d\n",ret-1);return;}
			}
		}
		else{
			for(j=l[i];j<=r[i];j++){
				las=gcd(las,A[j]);
				if(x%las==0){
					tmp=x/las;
					if((sxor[j]^lazy[i])==tmp){
						printf("%d\n",j-1);return;
					}
				}
			}
		}
		las=gcd(las,sgcd[i]);
	}
	puts("no");
}

int main(){
	int i,j,id;
	char cmd[10];
	ll x;
	scanf("%d",&N);
	for(i=1;i<=N;i++)scanf("%lld",&A[i]);
	Init();
	scanf("%d",&Q);
	for(i=1;i<=Q;i++){
		scanf("%s",cmd);
		if(cmd[0]=='M'){
			scanf("%d%lld",&id,&x);
			Modify(id+1,x);
		}
		else{
			scanf("%lld",&x);
			Query(x);
		}
	}
}