bzoj 4028 公约数数列

Posted on | Views:

分块.

$\mbox{xor}$ 显然就只是一个系数,用不上什么特殊性质.

考虑对序列分块,每个元素维护 $f(i)$ 表示从该块的 $l$ 到 $i$ 的前缀 $\gcd$ , $g(i)$ 表示从该块的 $l$ 到 $i$ 的前缀 $\mbox{xor}$ .

查询时依次处理每个块,记前面所有块的前缀 $\gcd$ 为 $pregcd$ ,前缀 $\mbox{xor}$ 为 $prexor$ .

前缀 $\gcd$ 是单调不升的,若加上这一块后, $pregcd$ 不变,则说明这一块的所有前缀 $gcd$ 都是 $pregcd$ .

此时只需要找一下这块内的第一个 $g(i) = \frac x {pregcd}\mbox{ xor } prexor$ ,这可以用 $map$ 预处理出来.

如果加上这一块后, $pregcd$ 会改变,就暴力枚举这个块内的每个位置,判断是否有解.

每次 $pregcd$ 减小时,都会至少减小到原来的一半,所以暴力枚举的位置最多 $O(\log a)$ 个.

修改时直接暴力重构所在的那一块即可.

时间复杂度 $O(m\cdot \sqrt n\cdot \log a)$ .

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
99
100
101
102
103
104
#include<bits/stdc++.h>
#define rg register
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}
const int MAXN=1e5+10,S=320;
int n,m,blocksiz,tot=0,L[S],R[S],bel[MAXN];
int a[MAXN],f[MAXN],g[MAXN];
map<ll,int> mp[S];
void init_block()
{
	blocksiz=sqrt(n);
	for(int i=1;i<=n;++i)
		bel[i]=(i-1)/blocksiz+1;
	tot=bel[n];
	for(int i=n;i>=1;--i)
		L[bel[i]]=i;
	for(int i=1;i<=n;++i)
		R[bel[i]]=i;
}
void calc_block(int x)
{
	mp[x].clear();
	f[L[x]]=g[L[x]]=a[L[x]];
	for(int i=L[x]+1;i<=R[x];++i)
	{
		f[i]=gcd(f[i-1],a[i]);
		g[i]=g[i-1]^a[i];
	}
	for(int i=R[x];i>=L[x];--i)
		mp[x][1LL*g[i]]=i;
}
int query(ll x)
{
	int pregcd=0,prexor=0;
	for(rg int i=1;i<=tot;++i)
	{
		if(gcd(pregcd,f[R[i]])==pregcd)
		{
			if(x%pregcd==0)
			{
				ll val=(x/pregcd)^prexor;
				if(mp[i].find(val)!=mp[i].end())
				return mp[i][val]-1;
			}
		}
		else
		{
			for(rg int j=L[i];j<=R[i];++j)
				if(1LL*(prexor^g[j])*gcd(pregcd,f[j])==x)
					return j-1;
		}
		pregcd=gcd(pregcd,f[R[i]]);
		prexor=prexor^g[R[i]];
	}
	return -1;
}
char op[10];
int main()
{
	n=read();
	init_block();
	for(rg int i=1;i<=n;++i)
		a[i]=read();
	for(rg int i=1;i<=tot;++i)
		calc_block(i);
	m=read();
	for(rg int i=1;i<=m;++i)
	{
		scanf("%s",op);
		if(op[0]=='M')//Modify
		{
			int id=read()+1,x=read();
			a[id]=x;
			calc_block(bel[id]);
		}
		else//Query
		{
			ll x;
			scanf("%lld",&x);
			int ans=query(x);
			if(ans!=-1)
				printf("%d\n",ans);
			else
				puts("no");
		}				
	}
	return 0;
}