loj 数列分块入门 5 样例过了,但测试点全WA
大佬们可以来康康是为什么吗?
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=5e4+5;
bool tag[N];
int n,size,a[N],f[N],s[N],e[N],all[N],add[N];
void turn(int l,int r){
if(f[l]==f[r]){
if(!tag[f[l]])for(int i=l;i<=r;i++)add[f[l]]-=a[i],a[i]=sqrt(a[i]),add[f[l]]+=a[i];
}else{
if(!tag[f[l]])for(int i=l;i<=e[f[l]];i++)add[f[l]]-=a[i],a[i]=sqrt(a[i]),add[f[l]]+=a[i];
if(!tag[f[r]])for(int i=s[f[r]];i<=r;i++)add[f[r]]-=a[i],a[i]=sqrt(a[i]),add[f[r]]+=a[i];
for(int i=f[l]+1;i<f[r];i++)if(!tag[i]){
bool flag=1;all[i]=0;
for(int j=s[i];j<=e[i];j++){
add[i]-=a[j],a[j]=sqrt(a[j]),add[i]+=a[j],all[i]+=a[j];
if(a[j]>1)flag=0;
}
if(flag)tag[i]=1;
}
}
}
int ask(int l,int r){
int cnt=0;
if(f[l]==f[r]){
if(tag[f[l]])cnt+=all[f[l]];else for(int i=l;i<=r;i++)cnt+=a[i];
}else{
if(tag[f[l]])cnt+=all[f[l]];else for(int i=l;i<=e[f[l]];i++)cnt+=a[i];
if(tag[f[r]])cnt+=all[f[r]];else for(int i=s[f[r]];i<=r;i++)cnt+=a[i];
for(int i=f[l]+1;i<f[r];i++)if(tag[i])cnt+=all[i];else cnt+=add[i];
}
return cnt;
}
signed main(){
cin>>n;size=sqrt(n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)
f[i]=(i-1)/size+1,e[f[i]]=i,add[f[i]]+=a[i];
for(int i=n;i>=1;i--)
s[f[i]]=i;
for(int i=1;i<=n;i++){
int opt,l,r,c;
scanf("%lld%lld%lld%lld",&opt,&l,&r,&c);
if(opt)printf("%lld\n",ask(l,r));else turn(l,r);
}
return 0;
}