P4145 上帝造题的七分钟2 / 花神游历各国

思路

每个数不会被开方超过log次，对每个数暴力开方即可

代码

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

#define int long long

using namespace std;

struct Node{

    int max,sum;

}Seg[100100<<2];

int a[100100],n,m;

void pushup(int o){

    Seg[o].sum=Seg[o<<1].sum+Seg[o<<1|1].sum;

    Seg[o].max=max(Seg[o<<1].max,Seg[o<<1|1].max);

}

void build(int l,int r,int o){

    if(l==r){

        Seg[o].sum=Seg[o].max=a[l];

        return;

    }

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

    build(l,mid,o<<1);

    build(mid+1,r,o<<1|1);

    pushup(o);

}

void modi(int L,int R,int l,int r,int o){

    if(Seg[o].max<=1)

        return;

    if(l==r){

        Seg[o].max=Seg[o].sum=sqrt(Seg[o].sum);

        return;

    }

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

    if(L<=mid)

        modi(L,R,l,mid,o<<1);

    if(R>mid)

        modi(L,R,mid+1,r,o<<1|1);

    pushup(o);

}

int query(int L,int R,int l,int r,int o){

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

        return Seg[o].sum;

    }

    int mid=(l+r)>>1,ans=0;

    if(L<=mid)

        ans+=query(L,R,l,mid,o<<1);

    if(R>mid)

        ans+=query(L,R,mid+1,r,o<<1|1);

    return ans;

}

signed main(){

    scanf("%lld",&n);

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

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

    build(1,n,1);

    scanf("%lld",&m);

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

        int opt,l,r;

        scanf("%lld %lld %lld",&opt,&l,&r);

        if(l>r)

            swap(l,r);

        if(opt==0)

            modi(l,r,1,n,1);

        else

            printf("%lld\n",query(l,r,1,n,1));

    }

    return 0;

}