BZOJ3211: 花神游历各国

#include<bits/stdc++.h>
#define il inline
#define RG register
#define ll long long
#define db double
#define N 100010
using namespace std;
int n,m,a[N];
namespace Tree{
  ll Sum[N*4];int cnt[N*4];
#define rs ((o<<1)|1)
#define ls (o<<1)
#define mid ((l+r)>>1)
  void build(int o,int l,int r){
    if(l==r){Sum[o]=a[l];return;}
    build(ls,l,mid),build(rs,mid+1,r);
    Sum[o]=Sum[rs]+Sum[ls];
  }
  void Modify(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
      cnt[o]++;
      if(l==r){Sum[o]=sqrt(Sum[o]);return;}
    }
    if(cnt[rs]<6&&mid<R)Modify(rs,mid+1,r,L,R);
    if(cnt[ls]<6&&mid>=L)Modify(ls,l,mid,L,R);
    Sum[o]=Sum[ls]+Sum[rs];
  }
  ll Query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R)return Sum[o];
    if(mid<L)return Query(rs,mid+1,r,L,R);
    else if(mid>=R)return Query(ls,l,mid,L,R);
    else return Query(rs,mid+1,r,L,R)+Query(ls,l,mid,L,R);
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;++i)scanf("%d",&a[i]);
  Tree::build(1,1,n);
  scanf("%d",&m);
  for(int i=1;i<=m;++i){
    int a,b,c;scanf("%d%d%d",&c,&a,&b);
    if(c==1)cout<<Tree::Query(1,1,n,a,b)<<"\n";
    else Tree::Modify(1,1,n,a,b);
  }
  return 0;
}