BZOJ 3211 花神游历各国 线段树题解

BZOJ 3211 花神游历各国 线段树题解

 

 

　　线段树区间修改区间查询，但是因为开方的特殊性，必须要更新到每个单点上。本题每个点最大为10⁹  ，开方五次就已经变成一了，所以开方标记超过五次往下就不用开了。

#include<cstdio>
#include<cmath> 
#include<algorithm>
#define left l,m,rt<<1
#define right m+1,r,rt<<1|1
#define int_ long long
const int maxn=100010;
using namespace std;
struct NODE{
    int_ sum;int mark;
}res[maxn<<2];
void push_up(int rt){
    res[rt].sum=res[rt<<1].sum+res[rt<<1|1].sum;
}
void build(int l,int r,int rt){
    if(l==r){
        scanf("%d",&res[rt].sum);
        return ;
    }
    int m=(l+r)>>1;
    build(left);
    build(right);
    push_up(rt);
}

void update(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        res[rt].mark++; 
        if(l==r){
            res[rt].sum=sqrt(res[rt].sum);
            return ;    
        }
    }
    if(res[rt].mark<=5){
        int m=(l+r)>>1;
        if(L<=m)update(L,R,left);
        if(R>m)update(L,R,right);
        push_up(rt);
    }
    
}
int_ enquiry(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R)return res[rt].sum;
    int_ ret=0;int m=(l+r)>>1;
    if(L<=m)ret+=enquiry(L,R,left);
    if(R>m)ret+=enquiry(L,R,right);
    return ret;
}
int main(){
    int n;
    scanf("%d",&n);
    build(1,n,1);
    int m;
    scanf("%d",&m);
    while(m--){
        int x,l,r;
        scanf("%d %d %d",&x,&l,&r);
        if(x==2)update(l,r,1,n,1);
        else printf("%lld\n",enquiry(l,r,1,n,1));
    }
    return 0;
}