【HEOI2015】公约数数列 题解（分块）

前言：毒瘤数据结构题，半个下午都在搞它了……

---------------------------

题目链接

题目大意：给定一个长度为$n$的序列，有两种操作：1.把$a_x$的值改成$y$。2.求一个最小的$p$使得$gcd(a_0,a_1,\cdots ,a_p)*XOR(a_0,a_1,\cdots ,a_p)=x$。

------------------------------

这种数据结构题一般只能用分块解决。线段树什么的不得T飞……

对于每个块，我们维护块内的$gcd$和$xor$和，还要记录以每个块的左端点为左端点的$xor$前缀和。

修改的时候直接$\sqrt n$暴力把所属块内的信息重新修改。

重点是查询。我们维护一个$pregcd$和$prexo$表示已经询问过的部分的$gcd$和$xor$和。有两种情况：

　　1.如果$gcd(pregcd,gcd[i])=pregcd$，那么二分查找块内可能符合条件的$p$。可以参考代码来理解。

　　2.如果不相等，那么暴力查找块内可能的$p$。

有一个性质：$A xor B=C$，那么$C xor B=A$。可以利用这个性质进行查询。

时间复杂度$O(n\sqrt n \log n)$。

代码：

/*记录每个块内的gcd，xor和；记录以每个块左端点为左端点的前缀xor和*/

#include<bits/stdc++.h>

#define int long long

using namespace std;

int gcd[],sumxo[],n,m,a[],block,tot,pregcd,prexo;

struct node{int sum,id;}xo[];

inline int read()

{

    int x=,f=;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-;ch=getchar();}

    while(isdigit(ch)){x=x*+ch-'';ch=getchar();}

    return x*f;

}

inline int GCD(int x,int y){if (!y) return x;return GCD(y,x%y);}

bool cmp(node x,node y){if(x.sum==y.sum) return x.id<y.id;return x.sum<y.sum;}

inline void build(int i)

{

    gcd[(i-)*block+]=sumxo[(i-)*block+]=a[(i-)*block+];

    xo[(i-)*block+]=(node){sumxo[(i-)*block+],(i-)*block+};

    for (int j=(i-)*block+;j<=min(n,i*block);j++)

    {

        gcd[j]=GCD(gcd[j-],a[j]);

        sumxo[j]=sumxo[j-]^a[j];

        xo[j]=(node){sumxo[j],j};

    }

    sort(xo+(i-)*block+,xo+min(n,i*block)+,cmp);

}

inline int half(int l,int r,int x)

{

    int mid,res=l;

    while(l<=r)

    {

        mid=(l+r)>>;

        if (xo[mid].sum>=x) res=mid,r=mid-;

        else l=mid+;

    }

    return res;

}

inline int query(int x)

{

    int ans=-;

    pregcd=a[],prexo=;

    for (int i=;i<=tot&&ans==-;i++)

    {

        if (GCD(pregcd,gcd[min(n,i*block)])==pregcd)

        {

            if (x%pregcd==)

            {

                int k=(x/pregcd)^prexo;

                int pos=half((i-)*block+,min(n,i*block),k);

                if(xo[pos].sum==k)

                {

                    ans=xo[pos].id;

                    break;

                }

            }

            pregcd=GCD(pregcd,gcd[min(n,i*block)]),prexo^=sumxo[min(n,i*block)];

        }

        else

        {

            for (int j=(i-)*block+;j<=min(n,i*block);j++)

            {

                pregcd=GCD(pregcd,a[j]);prexo^=a[j];

                if (pregcd*prexo==x){

                    ans=j;

                    break;

                }

            }

            if (ans!=-) break;

        }

    }

    return ans;

}

signed main()

{

    n=read();block=sqrt(n);

    tot=n/block;if (n%block) tot++;

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=tot;i++) build(i);

    m=read();

    while(m--)

    {

        string s;cin>>s;

        if (s[]=='M')

        {

            int x=read(),y=read();x++;

            a[x]=y;

            build((x-)/block+);

        }

        else

        {

            int x=read();

            int s=query(x);

            if (s==-) printf("no\n");

            else printf("%lld\n",s-);

        }

    }

    return ;

}

【HEOI2015】公约数数列 题解（分块）的相关教程结束。