传送门Can you answer these queries?

题意：线段树，只是区间修改变成把每个点的值开根号；

思路：对【X,Y】的值开根号，由于最大为 2⁶³.可以观察到最多开根号7次即为1，则当根号次数大于等于7时，这段区间值为R-L+1，还有一点是L可能大于R。

以下来自鸟神：（真是强啊）

据这一性质，我们可以得到一种解决方案：对于修改，我们对于区间内的数不全为1的区间更新，直到遇到区间内的数全部为1的区间或者叶子结点为止。这样只要使用线段树，维护区间和的信息即可。

#include <iostream>

#include <cstring>

#include <algorithm>

#include <string>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = ;

ll a[maxn],sum[maxn*];

int n,m;

void pushup(int rt)

{

    sum[rt]=sum[rt<<]+sum[rt<<|];

}

void buildup(int l,int r,int rt)

{

    if(l==r)

    {

        sum[rt]=a[l];

        return ;

    }

    int mid = (l+r)>>;

    buildup(l,mid,rt<<);

    buildup(mid+,r,rt<<|);

    pushup(rt);

}

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

{

    if(sum[rt]==r-l+)return ;    // 剪枝

    if(l==r)

    {

        sum[rt]=(int)sqrt(sum[rt]);

        return;

    }

    int mid=(l+r)>>;

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

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

    pushup(rt);

}

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

{

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

    {

        return sum[rt];

    }

    ll ans = ;

    int mid=(l+r)>>;

    if(mid>=L)ans+=query(L,R,l,mid,rt<<);

    if(R>mid)ans+=query(L,R,mid+,r,rt<<|);

    return ans;

}

int main(){

    int cnt=;

    while(~scanf("%d",&n))

    {

        printf("Case #%d:\n",++cnt);

        memset(a,,sizeof(a));

        memset(sum,,sizeof(sum));

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

        {

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

        }

        buildup(,n,);

        scanf("%d",&m);

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

        {

            int op,a,b;

            scanf("%d%d%d",&op,&a,&b);

            if(a>b)swap(a,b);

            if(op==)

            {

                ll ans = query(a,b,,n,);

                printf("%lld\n",ans);

            }

            else

            {

                update(a,b,,n,);

            }

        }

        printf("\n");

     }

    return ;

}

巴特西

HDU-4027-Can you answer these queries?线段树+区间根号+剪枝

传送门Can you answer these queries?

最新文章

热门文章