【线段树】上帝造题的七分钟 2

注意： 稍微暴力，注意开根号会使得数字急速变小。可以暴力改每一个位置上的值。

维护区间和，一个数最大是 2^64，如果继续开放操作最多每个叶子节点访问不超过32次，也就是最多访问 $4*n*32$ 次，时间复杂度很小，暴力维护就可以了。当 $sum[x]=r-l=1$也就是区间长度等于区间值的时候，此时开根号就不起作用了，因为此时区间内的所有值都是1 ，而$√1=1$，值不会发生变化

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
typedef long long ll;
ll sum[N<<2],lazy[N<<2],a[N<<2],p[N<<2];
int n,m;
void push(int x)
{
  sum[x]=sum[x<<1|1]+sum[x<<1];
}
void build(int x,int l,int r)
{
  if( l==r ) {sum[x]=a[l];return;}
  int mid=l+r>>1;
  build( x<<1,l,mid );
  build( x<<1|1,mid+1,r);
  push(x);
}
void update(int x,int l,int r,int L,int R,int v)
{
  if( r-l+1==sum[x] ) lazy[x]=1;
  if( lazy[x] ) return;
  if( l==r ) {
    a[l]=sqrt(a[l]);
    sum[x]=a[l];
    return;
  }
  int mid=l+r>>1;
  if( L<=mid ) update(x<<1,l,mid,L,R,v);
  if( R>mid ) update(x<<1|1,mid+1,r,L,R,v);
  push(x);
}
ll Sum(int x,int l,int r,int L,int R)
{
  if( L<=l and r<=R ) return sum[x];
  int mid=l+r>>1;
  ll ans=0;
  if( L<=mid ) ans+=Sum(x<<1,l,mid,L,R);
  if( R>mid ) ans+=Sum(x<<1|1,mid+1,r,L,R);
  return ans;
}

int main(){
  int w=1;
  cin>>n;
  {
  int o,x,y;
  ll z;
  for(int i=1;i<=n;i++)
  {
    scanf("%lld",&a[i]);
  }
  build(1,1,n);
  cin>>m;
  for(int i=1;i<=m;i++)
  {
    cin>>o>>x>>y;
    if( x>y ) swap(x,y);
    if( o )
    {
      cout<<Sum(1,1,n,x,y)<<'\n';
    }
    else{
      update(1,1,n,x,y,1);
    }
  }

  }
}