题解 P4108 【[HEOI2015]公约数数列】

wjyyy

2019-03-04 21:00:54

Solution

感觉需要推导的东西还是比较多的。但是以后要记着看到奇怪的(?)数据范围时要想到分块。 这个题有一定的特点,就是两个表达式都是前缀形式。对于 $\gcd$ 而言,它一定是递减的,而且不同的数值最多只有 $O(\log a_i)$ 个,因为每次至少会变为原来的 $\frac 12$。因此**产生变化的**位置是可以考虑枚举的。 注意到询问是 $10000$ 的,不是很大。我们对原区间进行 $O(\sqrt n)$ 分块。 因为要找的是最小的,所以应该从前往后枚举。对于 $\gcd$ 整块不变的那些块,我们只需要找到其中是否存在**异或前缀和**恰好为 $x/\gcd$ 的。这一询问可以用 `std::map` 来解决。 当涉及单点修改时,我们只需要对当前块中的 `map` 进行修改就可以了。 实际上 `map` 中存的是当前块中的异或前缀和,由于我们每次查询都是从前往后查,可以积累一定的信息。因此不必也不能维护全局前缀和,不然修改时影响的范围太大。 不过分块的细节挺多的,包括边界一类的。还要注意复杂度,不能把 `gcd()` 函数当 $O(1)$ 的操作用啊啊啊啊啊啊…= = 时间复杂度 $O(n\log a_i+q\sqrt n\log a_i)$。 ## Code: ```cpp #include<cstdio> #include<cstring> #include<map> #include<cmath> #define inf 2147438647 using std::map; int gcd(int x,int y) { while(y) { int t=y; y=x%y; x=t; } return x; } map<int,int> f[400]; int a[400][400],g[400][400]; int G[400],sum[400]; int main() { int n,m,u; scanf("%d",&n); int b=sqrt(n),tmp=0; for(int i=1;i<=n;++i) { int x=(i-1)/b,y=(i-1)%b+1; scanf("%d",&a[x][y]); tmp^=a[x][y]; g[x][y]=gcd(a[x][y],g[x][y-1]); G[x]=g[x][y]; if(f[x].find(tmp)==f[x].end()) f[x][tmp]=y; if(x!=i/b) { sum[x]=tmp; g[x+1][0]=G[x]; tmp=0; } } scanf("%d",&m); char op[100]; int tot=ceil((double)n/b)-1; while(m--) { scanf("%s",op); if(op[0]=='M') { scanf("%d",&u); ++u; int x=(u-1)/b,y=(u-1)%b+1; scanf("%d",&a[x][y]); f[x].clear(); tmp=0; g[x][0]=x?G[x-1]:0; for(int j=1;j<=b;++j) { tmp^=a[x][j]; if(f[x].find(tmp)==f[x].end()) f[x][tmp]=j; g[x][j]=gcd(a[x][j],g[x][j-1]); G[x]=g[x][j]; } sum[x]=tmp; } else { long long k; scanf("%lld",&k); int flag=0; tmp=0; int gtmp=a[0][1]; for(int i=0;i<=tot;++i) { if(!i||G[i]!=G[i-1])//暴力 { for(int j=1;j<=b;++j) { tmp^=a[i][j]; gtmp=g[i][j]; if((long long)tmp*gtmp==k) { flag=1; printf("%d\n",i*b+j-1); break; } } if(flag) break; } else { gtmp=G[i]; if(k%gtmp==0&&k/gtmp<inf&&f[i].find(k/gtmp^tmp)!=f[i].end()) { printf("%d\n",i*b+f[i][k/gtmp^tmp]-1); flag=1; break; } tmp^=sum[i]; } } if(flag) continue; puts("no"); } } return 0; } ```