BZOJ3211: 花神游历各国

3211: 花神游历各国

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 3751  Solved: 1361
[Submit][Status][Discuss]

Description

 

Input

 

Output

每次x=1时，每行一个整数，表示这次旅行的开心度

Sample Input

4

1 100 5 5

5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Sample Output

101

11

11

HINT

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

思路{

　　发现,一个数被开根号开最多6次就全变成1了.

　　那么用个数组记录一下开了几次,6次以上跳过.否则暴力修改.

}

#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)<<"
";
    else Tree::Modify(1,1,n,a,b);
  }
  return 0;
}