【BZOJ4028】[HEOI2015]公约数数列
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
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
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.
题解：做过magical GCD那题之后就知道这个套路了。一个序列的本质不同的前缀gcd只有log个（因为从左往右，gcd每次变化时都至少减半）。所以可以暴力维护每个gcd变化的位置。
然后问题变成了问你一个区间中是否存在一个位置x，使得1到x的异或和=val。考虑分块，块内排序。修改时小块暴力，大块打标记；查询时在块内二分查找有没有sum=val^tag的即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=100010;
typedef long long ll;
int n,m,B,gn;
int tag[1000],v[maxn],s[maxn],sp[maxn],g[100],gp[100],bg[1000];
char str[20];
inline ll rd()
{
ll ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int gcd(int a,int b)
{
return !b?a:gcd(b,a%b);
}
inline bool eql(ll a,ll b)
{
return (a==b)||((a)&&(b%a==0));
}
bool cmp(const int &a,const int &b)
{
return (s[a]==s[b])?(a<b):(s[a]<s[b]);
}
void getnxt()
{
int a=gp[gn]+1,c=a/B,i,j;
gn++,g[gn]=gcd(g[gn-1],v[a]);
for(j=a;j<c*B+B&&j<n;j++) if(!eql(g[gn],v[j])) {gp[gn]=j-1; return ;}
if(j==n) {gp[gn]=n-1; return ;}
for(i=c+1;i*B<n;i++) if(!eql(g[gn],bg[i])) break;
if(i*B>=n) {gp[gn]=n-1; return ;}
for(j=i*B;j<i*B+B&&j<n;j++) if(!eql(g[gn],v[j])) {gp[gn]=j-1; return ;}
gp[gn]=n-1; return ;
}
bool query(int x,ll val)
{
if(!eql(g[x],val)) return 0;
val=(!g[x])?val:val/g[x];
int a=gp[x-1]+1,b=gp[x],c=a/B,d=b/B,j;
if(c==d)
{
for(j=a;j<=b;j++) if((s[j]^tag[c])==val) {printf("%d
",j); return 1;}
return 0;
}
for(j=a;j<c*B+B;j++) if((s[j]^tag[c])==val) {printf("%d
",j); return 1;}
for(j=c+1;j<d;j++)
{
int l=j*B,r=j*B+B,mid;
while(l<r)
{
mid=(l+r)>>1;
if(s[sp[mid]]>=(val^tag[j])) r=mid;
else l=mid+1;
}
if(r<j*B+B&&s[sp[r]]==(val^tag[j])) {printf("%d
",sp[r]); return 1;}
}
for(j=d*B;j<=b;j++) if((s[j]^tag[d])==val) {printf("%d
",j); return 1;}
return 0;
}
int main()
{
n=rd(),B=int(sqrt(double(n)));
int i,j,a,c;
ll b,d;
for(i=0;i<n;i++) v[i]=rd();
gp[0]=-1,g[gn=1]=v[0];
for(i=0;i<n;i++)
{
if(i%B==0) tag[i/B+1]=tag[i/B],s[i]=v[i];
else s[i]=s[i-1]^v[i];
tag[i/B+1]^=v[i],bg[i/B]=gcd(v[i],bg[i/B]),sp[i]=i;
if(!eql(g[gn],v[i])) g[gn+1]=gcd(v[i],g[gn]),gp[gn]=i-1,gn++;
}
gp[gn]=n-1;
for(i=0;i<n;i+=B) sort(sp+i,sp+min(i+B,n),cmp);
m=rd();
for(i=1;i<=m;i++)
{
scanf("%s",str);
if(str[0]=='M')
{
a=rd(),b=rd(),c=a/B,d=v[a],v[a]=b,bg[c]=0;
for(j=c*B;j<min(c*B+B,n);j++) s[j]=(j==c*B)?v[j]:s[j-1]^v[j],sp[j]=j,bg[c]=gcd(bg[c],v[j]);
sort(sp+c*B,sp+min(c*B+B,n),cmp);
for(j=c+1;j*B<n;j++) tag[j]^=(b^d);
gn=0;
while(gp[gn]<n-1) getnxt();
}
else
{
b=rd();
for(j=1;j<=gn&&!query(j,b);j++);
if(j==gn+1) printf("no
");
}
}
return 0;
}