[BZOJ4028][HEOI2015]公约数数列(分块)

先发掘性质：

1.xor和gcd均满足交换律与结合率。

2.前缀gcd最多只有O(log)个。

但并没有什么数据结构能同时利用这两个性质，结合Q=10000，考虑分块。

对每块记录这几个信息：

1.块内所有数的gcd与异或和。

2.将块内所有前缀异或和放入一个数组排序。

查询时从前往后遍历每个块：

1.若当前块不使gcd改变，二分查找是否存在答案。

2.若改变，暴力查找答案。

复杂度（设块大小为S，值域为M)：

1.修改复杂度$O(S\log S)$

2.查询复杂度$O(S\log M+\frac{n}{S}\log S)$。

当$S=\sqrt{n}$时复杂度最优，为$O(Q\sqrt{n}\log n)$。

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 typedef long long ll;

 using namespace std;

 const int N=,K=;

 char op[];

 int n,B,tot,Q,ans,L[K],R[K];

 ll x,k,a[N],G[K],X[K];

 struct P{ ll x; int id; }p[N];

 bool operator <(const P &a,const P &b){ return (a.x==b.x) ? a.id<b.id : a.x<b.x; }

 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }

 void build(int x){

     G[x]=X[x]=a[L[x]]; p[L[x]]=(P){X[x],L[x]};

     rep(j,L[x]+,R[x]) G[x]=gcd(G[x],a[j]),X[x]^=a[j],p[j]=(P){X[x],j};

     sort(p+L[x],p+R[x]+);

 }

 int find(int l,int r,ll k){

     while (l<r){

         int mid=(l+r)>>;

         if (p[mid].x<k) l=mid+; else r=mid;

     }

     return r;

 }

 int main(){

     freopen("bzoj4028.in","r",stdin);

     freopen("bzoj4028.out","w",stdout);

     scanf("%d",&n); B=; tot=(n-)/B+;

     rep(i,,n) scanf("%lld",&a[i]);

     rep(i,,tot) L[i]=(i-)*B+,R[i]=min(n,i*B),build(i);

     for (scanf("%d",&Q); Q--; ){

         scanf("%s",op);

         if (op[]=='M') scanf("%lld%lld",&x,&k),x++,a[x]=k,build((x-)/B+);

         else{

             scanf("%lld",&x); ll g=a[],t=; bool w=;

             rep(i,,tot){

                 if (gcd(g,G[i])==g){

                     if (x%g==){

                         ll k=x/g^t; int ans=find(L[i],R[i],k);

                         if (p[ans].x==(x/g^t)){ printf("%d\n",p[ans].id-); w=; break; }

                     }

                     g=gcd(g,G[i]); t^=X[i];

                 }else

                     rep(j,L[i],R[i]){

                         g=gcd(g,a[j]); t^=a[j];

                         if (g*t==x){ printf("%d\n",j-); w=; break; }

                     }

                 if (w) break;

             }

             if (!w) puts("no");

         }

     }

     return ;

 }

巴特西

[BZOJ4028][HEOI2015]公约数数列(分块)

最新文章

热门文章