分块求助
  • 板块P2357 守墓人
  • 楼主银河AI
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/2/17 14:21
  • 上次更新2023/11/5 03:09:57
查看原帖
分块求助
209808
银河AI楼主2021/2/17 14:21

最后两个点不知道为什么wa了,有没有大佬帮我看一下

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+1;
ll n,f;
ll a[N],bel[N],lazy[N],st[N],ed[N],sum[N],block,len;
inline void init(){
	block=sqrt(n);
	len=ceil((double)n/block);
	for(ll i=1;i<=len;i++){
		for(ll j=(i-1)*block+1;j<=i*block;j++) bel[j]=i,sum[i]+=a[j];
		st[i]=(i-1)*block+1,ed[i]=i*block;
		if(i==len) ed[i]=n;
	}
}
inline void add(ll l,ll r,ll k){
	if(bel[l]==bel[r]){
		for(ll i=l;i<=r;i++) a[i]+=k;
		sum[bel[l]]+=k*(r-l+1);
	}		
	else{
		for(ll i=l;i<=ed[bel[l]];i++) a[i]+=k;
		for(ll i=st[bel[r]];i<=r;i++) a[i]+=k;
		sum[bel[l]]+=k*(ed[bel[l]]-l+1);sum[bel[r]]+=k*(r-st[bel[r]]+1);
		for(ll i=bel[l]+1;i<bel[r];i++) lazy[i]+=k,sum[i]+=k*(ed[i]-st[i]+1);
	}
}
inline void ask(ll l,ll r){
	ll ans=0;
	if(bel[l]==bel[r])
		for(ll i=l;i<=r;i++) ans+=(a[i]+lazy[bel[l]]);
	else{
		for(ll i=l;i<=ed[bel[l]];i++) ans+=(a[i]+lazy[bel[l]]);
		for(ll i=st[bel[r]];i<=r;i++) ans+=(a[i]+lazy[bel[r]]);
		for(ll i=bel[l]+1;i<bel[r];i++) ans+=sum[i];
	}
	printf("%lld\n",ans);
}
int t;
ll l,r,k;
int main(){
	scanf("%lld%lld",&n,&f);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	init();
	while(f--){
		scanf("%d",&t);
		if(t==1){
			scanf("%lld%lld%lld",&l,&r,&k);
			add(l,r,k);
		} 
		else if(t==2||t==3){
			scanf("%lld",&k);
			t==2?k=k:k=-k;
			add(1,1,k);
		}
		else if(t==4){
			scanf("%lld%lld",&l,&r);
			ask(l,r);
		}
		else ask(1,1);
	}
}
2021/2/17 14:21
加载中...