首页 > 代码库 > bzoj4028 [HEOI2015]公约数数列
bzoj4028 [HEOI2015]公约数数列
Description
设计一个数据结构. 给定一个正整数数列 a_0, a_1, ..., a_{n - 1}，你需要支持以下两种操作：
Input
输入数据的第一行包含一个正整数 n.
Output
对于每个 QUERY 询问，在单独的一行中输出结果。如果不存在这样的 p，输出 no.
Sample Input
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
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.
正解：分块。
这题太鬼畜了，完全想不到。。
首先这题正解是分块。我们分好块以后，计算出每个块的$gcd$前缀和和异或前缀和，分别用$g1[i]$和$g2[i]$表示。修改的时候我们就暴力修改整个块，并更新就行了，这里的复杂度，加上之后提到的$map$，复杂度是$O(\sqrt{n}logn)$的。
如何查询？我们记录一个$lastgcd$，表示当前访问的前一个块右端点到序列起点的$gcd$；$lastxor$类似。我们计算一下$\gcd(lastgcd,g1[R[i]])$，表示当前块最后一个端点的$gcd$前缀和。如果这个值与$lastgcd$相等，那么我们可以很快想到，这一个块内的$gcd$前缀和都相等，因为$gcd$是单调不增的。那么我们就是要找到满足$lastgcd*(g2[i] \ xor \ lastxor)=x$的i值，也就是满足$g2[i]=\frac{x}{lastgcd} \ xor \ lastxor$的值。这个我们开一个$map$统计一下$g2[i]$对应的$i$就行了，同时注意这个$map$在预处理和修改时都要更新。如果不满足这个条件呢？我们直接暴力搞整个块就行了。因为我们可以发现，$gcd$减小的时候，每次最小会除$2$，也就是说，$gcd$最多只会减小$log$次。那么我们暴力查询，是可以保证复杂度在$O(\sqrt{n}logn)$的。于是我们的总复杂度就是$O(q\sqrt{n}logn)$的。
$mdzz$这题还卡常数。。我要把$long \ long$改成$int$才能过。。
1 //It is made by wfj_2048~ 2 #include <algorithm> 3 #include <iostream> 4 #include <complex> 5 #include <cstring> 6 #include <cstdlib> 7 #include <cstdio> 8 #include <vector> 9 #include <cmath> 10 #include <queue> 11 #include <stack> 12 #include <map> 13 #include <set> 14 #define inf (1<<30) 15 #define N (100010) 16 #define il inline 17 #define RG register 18 #define ll long long 19 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 20 21 using namespace std; 22 23 map<int,int>mp[N]; 24 25 int a[N],bl[N],LL[N],RR[N],g1[N],g2[N],n,q,totb,block; 26 char s[12]; 27 28 il int gi(){ 29 RG int x=0,q=1; RG char ch=getchar(); 30 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 31 if (ch==‘-‘) q=-1,ch=getchar(); 32 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 33 return q*x; 34 } 35 36 il ll gll(){ 37 RG ll x=0,q=1; RG char ch=getchar(); 38 while ((ch<‘0‘ || ch>‘9‘) && ch!=‘-‘) ch=getchar(); 39 if (ch==‘-‘) q=-1,ch=getchar(); 40 while (ch>=‘0‘ && ch<=‘9‘) x=x*10+ch-48,ch=getchar(); 41 return q*x; 42 } 43 44 il int gcd(RG int a,RG int b){ return b ? gcd(b,a%b) : a; } 45 46 il void work(){ 47 n=gi(),block=sqrt(n),totb=(n-1)/block+1; 48 for (RG int i=1;i<=n;++i){ 49 a[i]=gi(),bl[i]=(i-1)/block+1; 50 if (!LL[bl[i]]) LL[bl[i]]=i; RR[bl[i]]=i; 51 } 52 for (RG int i=1;i<=totb;++i){ 53 RG int res1=0,res2=0; 54 for (RG int j=LL[i];j<=RR[i];++j){ 55 g1[j]=res1=gcd(res1,a[j]),g2[j]=res2=res2^a[j]; 56 if (!mp[i][g2[j]]) mp[i][g2[j]]=j; 57 } 58 } 59 q=gi(); 60 while (q--){ 61 scanf("%s",s); 62 if (s[0]==‘M‘){ 63 RG int id=gi()+1,x=gi(); a[id]=x; 64 RG int res1=0,res2=0,b=bl[id]; mp[b].clear(); 65 for (RG int j=LL[b];j<=RR[b];++j){ 66 g1[j]=res1=gcd(res1,a[j]),g2[j]=res2=res2^a[j]; 67 if (!mp[b][g2[j]]) mp[b][g2[j]]=j; 68 } 69 } else{ 70 RG ll x=gll(); RG int lastgcd=0,lastxor=0,ans=0; 71 for (RG int i=1;i<=totb;++i) 72 if (i!=1 && gcd(lastgcd,g1[RR[i]])==lastgcd){ 73 if (x%lastgcd){ 74 lastgcd=gcd(lastgcd,g1[RR[i]]); 75 lastxor^=g2[RR[i]]; continue; 76 } 77 RG ll k=(x/lastgcd)^lastxor; 78 if (k<=inf){ 79 RG int v=mp[i][k]; 80 if (v){ ans=v; break; } 81 } 82 lastgcd=gcd(lastgcd,g1[RR[i]]); 83 lastxor^=g2[RR[i]]; 84 } else{ 85 for (RG int j=LL[i];j<=RR[i];++j){ 86 lastgcd=gcd(lastgcd,a[j]),lastxor^=a[j]; 87 if ((ll)lastgcd*(ll)lastxor==x){ ans=j; break; } 88 } 89 } 90 if (ans) printf("%d\n",ans-1); else puts("no"); 91 } 92 } 93 return; 94 } 95 96 int main(){ 97 File("gcd"); 98 work(); 99 return 0;100 }
bzoj4028 [HEOI2015]公约数数列