Bash and a Tough Math Puzzle

wjh15101051's space

卧薪尝胆，厚积薄发。

Date: Wed Jul 11 18:19:36 CST 2018

In Category: NoCategory

Description：

一个序列支持单点修改，询问能否通过改变一个点的值使区间 $gcd$ 为 $x$ 。

$1\le N \le 5·10^5$

Solution：

用线段树维护序列，如果区间 $gcd$ 是 $x$ 的倍数，那么一定可以通过改一个得到。

如果区间 $gcd$ 不是 $x$ 的倍数，那么他的两个子区间一定只有一个区间 $gcd$ 不是 $x$ 的倍数，否则不合法，二分这个区间即可。

但询问的区间可能不是整块的，只要把所有区间找出来，不合法的一定只有一个，处理这个区间即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 500010

int a[MAXN];

int gcd(int a,int b){return (b == 0 ? a : gcd(b,a % b));}

int q;

#define mid ((l + r) >> 1)

struct edge

{

    int lc,rc;

    int g;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void pushup(int rt)

{

    t[rt].g = gcd(t[t[rt].lc].g,t[t[rt].rc].g);

    return;

}

void build(int &rt,int l,int r)

{

	rt = newnode();

    if(l == r)

    {

        t[rt].g = a[l];

        return;

    }

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    pushup(rt);

    return;

}

void change(int rt,int p,int k,int l,int r)

{

    if(l == r)

    {

        t[rt].g = k;

        return;

    }

    if(p <= mid)change(t[rt].lc,p,k,l,mid);

    else change(t[rt].rc,p,k,mid + 1,r);

    pushup(rt);

    return;

}

int al[MAXN],ar[MAXN],tot;

void get(int rt,int L,int R,int l,int r)

{

    if(L <= l && r <= R)

    {

        ++tot;

        a[tot] = rt;al[tot] = l;ar[tot] = r;

        return;

    }

    if(L <= mid)get(t[rt].lc,L,R,l,mid);

    if(R > mid)get(t[rt].rc,L,R,mid + 1,r);

    return;

}

bool check(int rt,int l,int r,int x)

{

    if(l == r)return true;

    int cnt = 0;

    if((t[t[rt].lc].g % x) != 0)++cnt; 

    if((t[t[rt].rc].g % x) != 0)++cnt;

    if(cnt > 1)return false;

    if((t[t[rt].lc].g % x) != 0)return check(t[rt].lc,l,mid,x);

    else return check(t[rt].rc,mid + 1,r,x);

}

void query(int L,int R,int x)

{

    tot = 0;

    get(root,L,R,1,n);

    int cnt = 0,p;

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

    {

        if(t[a[i]].g % x != 0)

        {

            ++cnt;p = i;

        }

    }

    if(cnt > 1)

    {

        puts("NO");

        return;

    }

    if(cnt == 0)

	{

		puts("YES");

		return;

	}

    if(check(a[p],al[p],ar[p],x))puts("YES");

    else puts("NO");

    return;

}

int main()

{

    scanf("%d",&n);

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

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

    build(root,1,n);

    memset(a,0,sizeof(a));

    scanf("%d",&q);

    int x,b,c,d;

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

    {

        scanf("%d",&x);

        if(x == 1)

        {

            scanf("%d%d%d",&b,&c,&d);

            query(b,c,d);

        }

        else

        {

            scanf("%d%d",&b,&c);

            change(root,b,c,1,n);

        }

    }

    return 0;

}

In tag: 数据结构-线段树

wjh15101051