设计一个数据结构. 给定一个正整数数列 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表示最大公约数。
设计一个数据结构. 给定一个正整数数列 a_0, a_1, ..., a_{n - 1}，你需要支持以下两种操作：
输入数据的第一行包含一个正整数 n.
对于每个 QUERY 询问，在单独的一行中输出结果。如果不存在这样的 p，输出 no.
对于 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.
正解：分块
解题报告：
看到数据范围我这种蒟蒻居然第一印象是分块，我真是太弱了。结果一看正解果然是分块，这就非常的优秀了。
维护每个块内的gcd、前缀异或和，修改的时候暴力修改块内即可。
考虑查询。因为我们要求一个前缀异或和×前缀gcd等于给定值y的最小下标，那么我们考虑做当前块的时候，如果当前gcd与之前所有的gcd（设为lastgcd）的gcd相等，由于前缀gcd一定是不增的。所以相等就意味着这个块的所有前缀gcd和lastgcd的gcd都是lastgcd，当前异或前缀和设为lastxor，存在在第i块中的前j个异或前缀和为X[i][j],则
lastgcd × （X[i][j]^lastxor）=y
则X[i][j]=(y/lastgcd)^lastxor，右边都是已知的
只需在当前块中查找有没有这种元素。
原来用的是map，居然TLE了，然后改成数组每次排序就可以了。调试了很久，写错了很多地方。。。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 #ifdef WIN32 14 #define OT "%I64d" 15 #else 16 #define OT "%lld" 17 #endif 18 using namespace std; 19 typedef long long LL; 20 const int MAXN = 100011; 21 int n,m,kuai,tot; 22 int belong[MAXN],L[MAXN],R[MAXN]; 23 char ch[10]; 24 LL G[401],X[401][401];//gcd、xor 25 LL a[MAXN]; 26 27 struct node{ 28 LL val; 29 int x; 30 }b[MAXN]; 31 32 inline int getint() 33 { 34 int w=0,q=0; 35 char c=getchar(); 36 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); 37 if (c==‘-‘) q=1, c=getchar(); 38 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); 39 return q ? -w : w; 40 } 41 42 inline LL getlong() 43 { 44 LL w=0,q=0; 45 char c=getchar(); 46 while((c<‘0‘ || c>‘9‘) && c!=‘-‘) c=getchar(); 47 if (c==‘-‘) q=1, c=getchar(); 48 while (c>=‘0‘ && c<=‘9‘) w=w*10+c-‘0‘, c=getchar(); 49 return q ? -w : w; 50 } 51 52 inline LL gcd(LL x,LL y){ if(y==0) return x; return gcd(y,x%y); } 53 inline bool cmp(node q,node qq){ if(q.val==qq.val) return q.x<qq.x; return q.val<qq.val; } 54 55 inline void work(){ 56 n=getint(); for(int i=1;i<=n;i++) a[i]=getint(); 57 kuai=sqrt(n); tot=n/kuai; if(n%kuai) tot++; 58 for(int i=1;i<=n;i++) { 59 belong[i]=(i-1)/kuai+1; 60 if(belong[i]!=belong[i-1]) L[belong[i]]=i; 61 R[belong[i]]=i; 62 } 63 int now; 64 for(int i=1;i<=n;i++) { 65 now=(i-1)%kuai+1; if(now==1) { G[belong[i]]=X[belong[i]][1]=a[i]; continue; } 66 G[belong[i]]=gcd(G[belong[i]],a[i]); 67 X[belong[i]][now]=X[belong[i]][now-1]^a[i]; 68 } 69 for(int i=1;i<=tot;i++) for(int j=1;j<=kuai;j++) b[(i-1)*kuai+j].val=X[i][j],b[(i-1)*kuai+j].x=(i-1)*kuai+j; 70 for(int i=1;i<=tot;i++) sort(b+L[i],b+R[i]+1,cmp); 71 m=getint(); int x; LL y; 72 LL lastgcd,xr,find; int l,r,mid,wei; 73 while(m--) { 74 scanf("%s",ch); 75 if(ch[0]==‘M‘) { 76 x=getint()+1; y=getlong(); 77 //mp[belong[x]].clear(); 78 a[x]=y; X[belong[x]][1]=G[belong[x]]=a[L[belong[x]]]; 79 for(int i=L[belong[x]]+1;i<=R[belong[x]];i++) G[belong[x]]=gcd(G[belong[x]],a[i]),X[belong[x]][(i-1)%kuai+1]=X[belong[x]][(i-1)%kuai]^a[i]; 80 for(int i=L[belong[x]];i<=R[belong[x]];i++) b[i].val=X[belong[x]][(i-1)%kuai+1],b[i].x=i; 81 sort(b+L[belong[x]],b+R[belong[x]]+1,cmp); 82 }else{ 83 y=getlong(); lastgcd=0; xr=0; 84 bool ok=false; 85 for(int i=1;i<=tot;i++) { 86 if(i==1 || gcd(G[i],lastgcd)!=lastgcd) {//暴力做 87 for(int j=1;j<=kuai;j++) { 88 lastgcd=gcd(lastgcd,a[j+(i-1)*kuai]); 89 xr^=a[j+(i-1)*kuai]; 90 if(xr*lastgcd==y) { printf("%d\n",(i-1)*kuai+j-1); ok=true; break; } 91 } 92 if(ok) break; 93 } 94 else{//可以利用性质直接查找 95 LL search=y/lastgcd; 96 if(y%lastgcd==0) { 97 find=search^xr; 98 l=L[i],r=R[i]; wei=0; 99 while(l<=r) { mid=(l+r)/2; if(b[mid].val>=find) wei=mid,r=mid-1; else l=mid+1; } 100 if(b[wei].val==find) { printf("%d\n",b[wei].x-1); ok=true; } 101 } 102 xr^=X[i][kuai]; lastgcd=gcd(lastgcd,G[i]); 103 } 104 if(ok) break; 105 } 106 if(!ok) printf("no\n"); 107 } 108 } 109 } 110 111 int main() 112 { 113 work(); 114 return 0; 115 }
原文：http://www.cnblogs.com/ljh2000-jump/p/5738557.html