4028: [HEOI2015]公约数数列

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4028

Description

设计一个数据结构. 给定一个正整数数列 a_0, a_1, ..., a_{n - 1}，你需要支持以下两种操作：

MODIFY id x: 将 a_{id} 修改为 x.
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表示最大公约数。

Input

输入数据的第一行包含一个正整数 n.

接下来一行包含 n 个正整数 a_0, a_1, ..., a_{n - 1}.

之后一行包含一个正整数 q，表示询问的个数。

之后 q 行，每行包含一个询问。格式如题目中所述。

Output

对于每个 QUERY 询问，在单独的一行中输出结果。如果不存在这样的 p，输出 no.

Sample Input

1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640

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

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，肯定GCD在不断的减小的，而且每次减小最少都是除以2的

所以前缀gcd的种类最多logn种

于是我们就分块搞

那hash表把每一块的xor都存下来

如果这一块内的gcd不变的话，我就直接拿这一块的hash表去查询就好了

如果gcd变化了，就直接暴力这一块

复杂度是n*sqrtn*logn(其实我感觉这个复杂度和暴力没啥区别

在bzoj上map会tle，所以我用的set

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+7;

int a[maxn];

int l[1000],r[1000];

int block,num,belong[maxn];

int Gcd[maxn],Xor[maxn];

set<int> S[1000];

int gcd(int a,int b)

{

    if(b==0)return a;

    return gcd(b,a%b);

}

void build(int t)

{

    S[t].clear();

    Gcd[l[t]]=a[l[t]],Xor[l[t]]=a[l[t]];

    S[t].insert(Xor[l[t]]);

    for(int i=l[t]+1;i<=r[t];i++)

    {

        Gcd[i]=gcd(Gcd[i-1],a[i]),Xor[i]=Xor[i-1]^a[i];

        S[t].insert(Xor[i]);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d",&a[i]);

    block=(int)sqrt(n+0.5);

    num = n/block;

    if(n%block)num++;

    for(int i=1;i<=num;i++)

        l[i]=(i-1)*block+1,r[i]=i*block;

    r[num]=n;

    for(int i=1;i<=n;i++)

        belong[i]=(i-1)/block+1;

    for(int i=1;i<=num;i++)

        build(i);

    int q;scanf("%d",&q);

    while(q--)

    {

        char s[10];

        scanf("%s",s);

        if(s[0]=='M')

        {

            int x,y;

            scanf("%d%d",&x,&y);x++;

            a[x]=y;build(belong[x]);

        }

        else

        {

            long long x;scanf("%lld",&x);

            int flag = 0,Lgcd=0,Lxor=0;

            for(int i=1;i<=num;i++)

            {

                int T = gcd(Lgcd,Gcd[r[i]]);

                if(T!=Lgcd)

                {

                    for(int j=l[i];j<=r[i];j++)

                        if((long long)(Xor[j]^Lxor)*(long long)(gcd(Lgcd,Gcd[j]))==x)

                        {

                            flag = j;

                            break;

                        }

                    if(flag>0)break;

                }

                else

                {

                    if(x%T==0&&S[i].count((int)(x/T)^Lxor))

                    {

                        for(int j=l[i];j<=r[i];j++)

                            if((long long)(Xor[j]^Lxor)*(long long)(gcd(Lgcd,Gcd[j]))==x)

                            {

                                flag = j;

                                break;

                            }

                        if(flag>0)break;

                    }

                }

                Lgcd = T,Lxor^=Xor[r[i]];

            }

            if(flag>0)

                printf("%d\n",flag-1);

            else

                printf("no\n");

        }

    }

}

巴特西

BZOJ 4028: [HEOI2015]公约数数列分块

4028: [HEOI2015]公约数数列

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

巴特西

BZOJ 4028: [HEOI2015]公约数数列 分块

4028: [HEOI2015]公约数数列

题目连接：

Description

Input

Output

Sample Input

Sample Output

Hint

题意

题解：

代码

最新文章

热门文章

BZOJ 4028: [HEOI2015]公约数数列分块