首页 > 代码库 > bzoj4028: [HEOI2015]公约数数列
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.
分块维护 块内gcd 以及 块内出现的每个异或前缀和及位置，修改可以暴力重构整个块，查询则利用gcd的性质，由于前缀gcd的取值种数是对数级的，对前缀gcd不变的块二分查询，前缀gcd改变的块暴力计算，总复杂度约为O(nsqrt(n)log(max(a_i)))
#include<cstdio>#include<cmath>#include<algorithm>char buf[5000007],*ptr=buf-1;template<class T>void _(T&x){ int c=*++ptr; x=0; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr;}int _c(){ int c=*++ptr; while(c>‘Z‘||c<‘A‘)c=*++ptr; int r=c; while(c>=‘A‘&&c<=‘Z‘)c=*++ptr; return r;}bool dt[555];int n,q,a[100007],B,id[100007],ls[555],rs[555],gs[555];int xa[555];struct pos{ int x,y; bool operator<(pos w)const{return y!=w.y?y<w.y:x<w.x;}}vs[100007];int gcd(int a,int b){ for(int c;b;c=a,a=b,b=c%b); return a;}int bit[100007];void xadd(int w,int a){ for(;w<=n;w+=w&-w)bit[w]^=a;}int xsum(int w){ int s=0; for(;w;w-=w&-w)s^=bit[w]; return s;}int main(){ fread(buf,1,sizeof(buf),stdin); _(n); B=sqrt(n); for(int i=1;i<=n;++i)_(a[i]),id[i]=(i-1)/B,xadd(i,a[i]); for(int i=0;i<=id[n];++i)ls[i]=i*B+1,rs[i]=ls[i]+B-1,dt[i]=1; rs[id[n]]=n; for(_(q);q;--q){ if(_c()==‘M‘){ int x,y,z; _(x);_(y); ++x; z=a[x]^y; xadd(x,z); a[x]=y; int b=id[x]; dt[b]=1; for(int i=b+1;i<=id[n];++i)xa[i]^=z; }else{ long long x; _(x); for(int i=0,gl=0;i<=id[n];++i){ if(dt[i]){ dt[i]=xa[i]=gs[i]=0; int sl=xsum(ls[i]-1); for(int j=ls[i];j<=rs[i];++j){ gs[i]=gcd(gs[i],a[j]); sl^=a[j]; vs[j]=(pos){j,sl}; } std::sort(vs+ls[i],vs+rs[i]+1); } int g=gcd(gl,gs[i]); if(gl!=g){ int sl=xsum(ls[i]-1); for(int j=ls[i];j<=rs[i];++j){ gl=gcd(gl,a[j]); sl^=a[j]; if(1ll*gl*sl==x){ printf("%d\n",j-1); goto o; } } }else if(x%gl==0&&x/gl<1073741824){ int z=x/gl^xa[i]; pos*it=std::lower_bound(vs+ls[i],vs+rs[i]+1,(pos){0,z}); if(it!=vs+rs[i]+1&&it->y==z){ printf("%d\n",it->x-1); goto o; } } } puts("no"); o:; } } return 0;}
bzoj4028: [HEOI2015]公约数数列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。