题意:

给你n个数,两个操作

1,询问区间内的gcd是否可以在修改最多一个数的情况下为x

2,修改一个数

n<=5e5 q<=4e5

=============

做法1:

线段树

区间维护,查询的时候只要看区间内是否gcd %x==0

如果不为0,则继续查询里面(如果已经有一个%x!=0的那就直接返回答案错误)

我写的比较差,好像复杂度O(n log^3 n)

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int gcd(int x,int y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}
int val[1<<20];
int a[500005];
void build_tree(int num,int l,int r)
{
    if (l==r-1)
    {
        val[num]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build_tree(num*2+1,l,mid);
    build_tree(num*2+2,mid,r);
    val[num]=gcd(val[num*2+1],val[num*2+2]);
}
void change(int num,int l,int r,int l0,int k)
{
    if (l==r-1)
    {
        val[num]=k;
        return;
    }
    int mid=(l+r)/2;
    if (l0<mid)
    {
        change(num*2+1,l,mid,l0,k);
    }
    else
    {
        change(num*2+2,mid,r,l0,k);
    }
    val[num]=gcd(val[num*2+1],val[num*2+2]);
}
int query_ans(int num,int l,int r,int l0,int r0)
{
    if ((l0<=l)&&(r<=r0))
    {
        return val[num];
    }
    int mid=(l+r)/2;
    int ans=0;
    if (l0<mid) ans=gcd(query_ans(num*2+1,l,mid,l0,r0),ans);
    if (mid<r0) ans=gcd(query_ans(num*2+2,mid,r,l0,r0),ans);
    return ans;
}
int query(int num,int l,int r,int l0,int r0,int x)
{
    if (query_ans(num,l,r,l0,r0)%x==0)
    {
        return 0;
    }
    if (l==r-1)
    {
        return 1;
    }
    int mid=(l+r)/2;
    int t=0;
    if (l0<mid)
    {
        if (query_ans(num*2+1,l,mid,l0,r0)%x!=0)
        {
            t+=query(num*2+1,l,mid,l0,r0,x);
            if (t>=2) return t;
        }
    }
    if (mid<r0)
    {
        if (query_ans(num*2+2,mid,r,l0,r0)%x!=0)
        {
            if (t==1) return 2;
            t+=query(num*2+2,mid,r,l0,r0,x);
            if (t>=2) return t;
        }
    }
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int q;
    scanf("%d",&q);
    build_tree(0,0,n);
    for (i=0;i<q;i++)
    {
        int oper;
        int x;
        scanf("%d",&oper);
        if (oper==1)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            l--;
            scanf("%d",&x);
            if (query(0,0,n,l,r,x)>1)
            {
                puts("NO");
            }
            else
            {
                puts("YES");
            }
        }
        else
        {
            int t;
            scanf("%d",&t);
            t--;
            scanf("%d",&x);
            change(0,0,n,t,x);
        }
    }
    return 0;
}

做法2:

三级分块?

分成50个大块,每个大块里面100个小块,每个小块里面100个数字

暴力修改,分块一样的查询

复杂度O(n sqrt_3(n))

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<time.h>
#include<math.h>
#include<memory>
#include<vector>
#include<bitset>
#include<fstream>
#include<stdio.h>
#include<utility>
#include<sstream>
#include<string.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int block=100;
inline int gcd(int x,int y)
{
    if (y==0) return x;
    return gcd(y,x%y);
}
int a[500005];
int gcds[55];
int gcd_mid[5005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int j,k;
    for (i=0;i<50;i++)
    {
        gcds[i]=0;
        for (j=0;j<block;j++)
        {
            gcd_mid[i*100+j]=0;
            for (k=0;k<block;k++)
            {
                gcd_mid[i*100+j]=gcd(a[i*10000+j*100+k],gcd_mid[i*100+j]);
            }
            gcds[i]=gcd(gcd_mid[i*100+j],gcds[i]);
        }
    }
    int q;
    scanf("%d",&q);
    for (i=0;i<q;i++)
    {
        int oper;
        scanf("%d",&oper);
        if (oper==1)
        {
            int l,r,x;
            scanf("%d%d%d",&l,&r,&x);
            l--;
            int sum=0;
            for (;;)
            {
                if (l>=r) break;
                if (l%10000==0)
                {
                    if (l+10000<=r)
                    {
                        if (gcds[l/10000]%x==0)
                        {
                            l+=10000;
                            continue;
                        }
                        else
                        {
                            if (sum==1)
                            {
                                sum++;
                                break;
                            }
                        }
                    }
                }
                if (l%100==0)
                {
                    if (l+100<=r)
                    {
                        if (gcd_mid[l/100]%x==0)
                        {
                            l+=100;
                            continue;
                        }
                        else
                        {
                            if (sum==1)
                            {
                                sum++;
                                break;
                            }
                        }
                    }
                }
                if (a[l]%x!=0)
                {
                    sum++;
                    if (sum==2) break;
                }
                l++;
            }
            if (sum>=2)
            {
                puts("NO");
            }
            else
            {
                puts("YES");
            }
        }
        else
        {
            int pos,x;
            scanf("%d%d",&pos,&x);
            pos--;
            a[pos]=x;
            int t=pos/100*100;
            int j;
            gcd_mid[t/100]=x;
            for (j=t;j<t+100;j++)
            {
                gcd_mid[t/100]=gcd(a[j],gcd_mid[t/100]);
            }
            t/=100;
            t=t/100*100;
            gcds[t/100]=0;
            for (j=t;j<t+100;j++)
            {
                gcds[t/100]=gcd(gcd_mid[j],gcds[t/100]);
            }
        }
    }
    return 0;
}