bzoj4028

扫码查看

一眼分块题……

分块,维护每个块的总的gcd和xor和

先思考我们应该怎么查询,考虑到gcd是一个神奇的东西,因为它最多变化logX次

于是我们从前往后扫描每个块,如果一个块内总的gcd是当前扫描的前缀gcd的倍数

那么,也就意味着这个块里的每个位置所对应的前缀的gcd都等于当前gcd

因此,我们设当前xor和为nowxor,gcd为nowgcd,partxor为块内某个块前缀xor和

nowxor xor partxor*nowgcd=x 即 nowxor xor (x/nowgcd)=partxor

这时候只要查询块内是否存在某个块前缀xor和为nowxor xor (x/nowgcd)即可,这我们可以用hash解决

如果不是倍数关系,那么我们直接暴力这个块即可,这样的暴力一定不会超过logX次

至于修改,我们直接暴力重构对应块即可

 const mo=;
type node=record
po,num,next:longint;
end; var e:array[..] of node;
p:array[..,..mo] of longint;
a,g,b,be:array[..] of longint;
size,t,len,i,j,n,m,x,y:longint;
z:int64;
ch:char;
s:string; function gcd(a,b:longint):longint;
begin
if b= then exit(a)
else exit(gcd(b,a mod b));
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure work(x,y,z:longint);
var i,j:longint;
begin
i:=p[x,y mod mo];
while i<> do
begin
j:=e[i].po;
if e[i].po=y then
begin
e[i].num:=min(e[i].num,z);
exit;
end;
i:=e[i].next;
end;
inc(len);
e[len].po:=y;
e[len].num:=z;
e[len].next:=p[x,y mod mo];
p[x,y mod mo]:=len;
end; procedure del(x,y,z:longint);
var i,j:longint;
begin
i:=p[x,y mod mo];
while i<> do
begin
j:=e[i].po;
if e[i].po=y then
begin
if e[i].num=z then e[i].num:=n+;
exit;
end;
i:=e[i].next;
end;
end; function get(x,y:longint):longint;
var i,j:longint;
begin
i:=p[x,y mod mo];
while i<> do
begin
j:=e[i].po;
if j=y then exit(e[i].num);
i:=e[i].next;
end;
exit(n+);
end; function ask(x:int64):longint;
var tg,tx,i,j,r,p:longint;
begin
tg:=; tx:=;
for i:= to size do
begin
tg:=gcd(tg,a[i]);
tx:=tx xor a[i];
if int64(tg)*int64(tx)=x then exit(i);
if x div int64(tg)> shl then exit(-);
end;
for i:= to t do
begin
if x div int64(tg)> shl then exit(-);
if i=t then r:=n else r:=i*size;
if g[r] mod tg= then
begin
if x mod tg= then
begin
p:=get(i,tx xor (x div int64(tg)));
if p<=n then exit(p);
end;
tx:=tx xor b[r];
end
else begin
for j:=(i-)*size+ to r do
begin
tg:=gcd(tg,a[j]);
tx:=tx xor a[j];
if int64(tg)*int64(tx)=x then exit(j);
if x div int64(tg)> shl then exit(-);
end;
end;
end;
exit(-);
end; begin
readln(n);
size:=trunc(sqrt(n));
for i:= to n do
begin
read(a[i]);
be[i]:=(i-) div size+;
end;
t:=n div size;
if n mod size<> then inc(t);
for i:= to n do
begin
if i mod size= then
begin
g[i]:=a[i];
b[i]:=a[i];
end
else begin
b[i]:=b[i-] xor a[i];
g[i]:=gcd(g[i-],a[i]);
end;
work(be[i],b[i],i);
end;
readln(m);
for i:= to m do
begin
s:='';
read(ch);
while ch<>' ' do
begin
s:=s+ch;
read(ch);
end;
if s[]='M' then
begin
readln(x,y);
inc(x);
a[x]:=y;
for j:=x to min(size*be[x],n) do
begin
del(be[x],b[j],j);
if j mod size= then
begin
b[j]:=a[j];
g[j]:=a[j];
end
else begin
b[j]:=b[j-] xor a[j];
g[j]:=g[j-] xor a[j];
end;
work(be[x],b[j],j);
end;
end
else begin
readln(z);
x:=ask(z);
if x=- then writeln('no') else writeln(x-);
end;
end;
end.
04-26 16:51
查看更多