水一道入门分块qwq
题面: 开方基本暴力。。 如果某一个区间全部都开成1或0就打上标记全部跳过就行了 因为一个数开上个四五六次就是1了所以复杂度能过233~code:
//By Menteur_Hxy#include#include #include #include #include using namespace std;int rd() { int x=0,fla=1; char c=' '; while(c>'9'|| c<'0') { if(c=='-') fla=-fla; c=getchar();} while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar(); return x*fla;}const int MAX=50010;const int INF=0x3f3f3f3f;int n,blo;int v[MAX],fla[MAX],sum[MAX],bl[MAX];void sqr(int x) { if(fla[x]) return ; fla[x]=1;sum[x]=0; for(int i=(x-1)*blo+1;i<=x*blo;i++) { v[i]=sqrt(v[i]),sum[x]+=v[i]; if(v[i]>1) fla[x]=0; }}void add(int a,int b,int c) { for(int i=a;i<=min(bl[a]*blo,b);i++) { sum[bl[a]]-=v[i]; v[i]=sqrt(v[i]); sum[bl[a]]+=v[i]; } if(bl[a]!=bl[b]) for(int i=(bl[b]-1)*blo+1;i<=b;i++) { sum[bl[b]]-=v[i]; v[i]=sqrt(v[i]); sum[bl[b]]+=v[i]; } for(int i=bl[a]+1;i<=bl[b]-1;i++) sqr(i);}int query(int a,int b) { int ans=0; for(int i=a;i<=min(bl[a]*blo,b);i++) ans+=v[i]; if(bl[a]!=bl[b]) for(int i=(bl[b]-1)*blo+1;i<=b;i++) ans+=v[i]; for(int i=bl[a]+1;i<=bl[b]-1;i++) ans+=sum[i]; return ans;}int main() { n=rd(); blo=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1;i<=n;i++) { bl[i]=(i-1)/blo+1; sum[bl[i]]+=v[i]; } for(int i=1;i<=n;i++) { int opt=rd(),a=rd(),b=rd(),c=rd(); if(opt) printf("%d\n",query(a,b)); else add(a,b,c); } return 0;}