蒟蒻求助
  • 板块学术版
  • 楼主y0y68
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/6/11 21:49
  • 上次更新2023/11/7 00:49:52
查看原帖
蒟蒻求助
115668
y0y68楼主2020/6/11 21:49

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;
}
2020/6/11 21:49
加载中...