洛谷P4145上帝造题的七分钟—

题目：https://www.luogu.org/problemnew/show/P4145

区间开平方，可以发现其实开几次就变成1，不需要开了，所以标记一下，每次只去开需要开的地方；

原来写的并查集跳过1或0，然而WA...其实是没有记录原数组的值，因为树状数组存的是修改量；

(如果a数组<原数组>开int会RE！)

改成线段树，本来想着是这一段区间和只要小于等于其长度就可以跳过了，然而仔细想想完全不是，应为可能有多个0什么的；

所以直接开bool数组标记一下就好了；

不需要pushdown，直接去修改或是跳过。

并查集：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long ll;

int const MAXN=;

int n,m,a[MAXN],fa[MAXN];

ll f[MAXN];

int find(int x)

{

    if(x==fa[x])return x;

    return fa[x]=find(fa[x]);

}

void add(int x,ll y)

{

    for(;x<=n;x+=(x&-x))

        f[x]+=y;

}

void update(int x)

{

    int tmp=a[x];

    a[x]=sqrt(a[x]);

    if(a[x]==||a[x]==)fa[x]=find(x+);

    add(x,a[x]-tmp);

//    for(;x<=n;x+=(x&-x))

//        f[x]-=tmp,f[x]+=a[x];

}

ll query(int x)

{

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

//        printf("%d ",a[i]);

//    printf("\n");

    ll sum=;

    for(;x;x-=(x&-x))

        sum+=f[x];

    return sum;

}

int main()

{

    scanf("%d",&n);

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

    {

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

        fa[i]=i;

        add(i,a[i]);

    }

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

//        printf("%lld ",f[i]);

//    printf("\n");

    fa[n+]=n+;

    scanf("%d",&m);

    while(m--)

    {

        int t,l,r;

        scanf("%d%d%d",&t,&l,&r);

        if(l>r)swap(l,r);

        if(t==)

        {

            int x=find(l);

            while(x<=r)

            {

                update(x);

                x=find(x+);

//                cout<<x<<endl;

            }

        }

        if(t==)

        {

            ll s1=,s2=;

            if(l-)s1=query(l-);

            s2=query(r);

//            printf("s1=%lld s2=%lld\n",s1,s2);

            printf("%lld\n",s2-s1);

        }

    }

    return ;

}

囧

代码如下：

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long ll;

int const MAXN=;

int n,m;

ll tr[MAXN<<],a[MAXN];

bool tg[MAXN<<];

void pushup(int nw)

{

    tr[nw]=tr[nw<<]+tr[nw<<|];

    tg[nw]=(tg[nw<<]&&tg[nw<<|]);

}

//void pushdown(int l,int r,int nw)

//{

//    if(l==r)

//    {

//        tr[nw]=sqrt(tr[nw]);

//        return;

//    }

//    while(lz[nw])

//    {

//        if(tr[nw]<=r-l+1)

//        {

//            lz[nw]=0;

//            break;

//        }

//        int mid=((l+r)>>1);

//        if(tr[nw<<1]>mid-l+1)pushdown(l,mid,nw<<1);

//        if(tr[nw<<1|1]>r-mid)pushdown(mid+1,r,nw<<1|1);

//        pushup(nw);

//        lz[nw]--;

//    }

//}

void update(int l,int r,int L,int R,int nw)

{

    if(tg[nw])return;

    if(l==r)

    {

        tr[nw]=(ll)sqrt(tr[nw]);

        if(tr[nw]==||tr[nw]==)tg[nw]=;

        return;

    }

    int mid=((l+r)>>);

    if(mid>=L)update(l,mid,L,R,nw<<);

    if(mid<R)update(mid+,r,L,R,nw<<|);

    pushup(nw);

}

ll query(int l,int r,int L,int R,int nw)

{

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

//        printf("%d ",a[i]);

//    printf("\n");

    ll sum=;

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

    {

//        pushdown(l,r,nw);

        return tr[nw];

    }

    int mid=((l+r)>>);

    if(mid>=L)sum+=query(l,mid,L,R,nw<<);

    if(mid<R)sum+=query(mid+,r,L,R,nw<<|);

    return sum;

}

void build(int l,int r,int nw)

{

    if(l==r)

    {

        tr[nw]=a[l];

        if(a[l]==||a[l]==)tg[nw]=;

        return;

    }

    int mid=((l+r)>>);

    build(l,mid,nw<<);

    build(mid+,r,nw<<|);

    pushup(nw);

}

int main()

{

    scanf("%d",&n);

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

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

    scanf("%d",&m);

    build(,n,);

    while(m--)

    {

        int d,x,y;

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

        if(x>y)swap(x,y);

        if(d==)update(,n,x,y,);

        if(d==)printf("%lld\n",query(,n,x,y,));

    }

    return ;

}

巴特西

洛谷P4145上帝造题的七分钟——区间修改

最新文章

热门文章