bzoj3211 花神游历各国

传送门

分析

因为所有数均小于1e9，所以只需要开根几次就会变成1。因此我们只需要维护区间和以及这个区间是否全部小于等于1即可，每一次暴力修改区间内的还不是1或0的数即可。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<ctime>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
long long d[440000],is[440000];
inline void build(long long le,long long ri,long long wh,long long pl,long long k){
      d[wh]+=k;
      if(le==ri)return;
      long long mid=(le+ri)>>1;
      if(mid>=pl)build(le,mid,wh<<1,pl,k);
        else build(mid+1,ri,wh<<1|1,pl,k);
}
inline void update(long long le,long long ri,long long wh,long long x,long long y){
      if(le==ri){
          d[wh]=sqrt(d[wh]);
          if(d[wh]<=1)is[wh]=1;
          return;
      }
      long long mid=(le+ri)>>1;
      if(mid>=x&&!is[wh<<1])update(le,mid,wh<<1,x,y);
      if(mid<y&&!is[wh<<1|1])update(mid+1,ri,wh<<1|1,x,y);
      d[wh]=d[wh<<1]+d[wh<<1|1];
      is[wh]=is[wh<<1]&is[wh<<1|1];
}
inline long long q(long long le,long long ri,long long wh,long long x,long long y){
      if(le>=x&&ri<=y)return d[wh];
      long long mid=(le+ri)>>1,ans=0;
      if(mid>=x)ans+=q(le,mid,wh<<1,x,y);
      if(mid<y)ans+=q(mid+1,ri,wh<<1|1,x,y);
      return ans;
}
int main(){
      long long n,m,i,j,k,x,y;
      scanf("%lld",&n);
      for(i=1;i<=n;i++){
          scanf("%lld",&x);
          build(1,n,1,i,x);
      }
      scanf("%lld",&m);
      for(i=1;i<=m;i++){
          scanf("%lld%lld%lld",&k,&x,&y);
          if(k==1)printf("%lld
",q(1,n,1,x,y));
          else update(1,n,1,x,y);
      }
      return 0;
}