社区讨论

为啥别人都是最后一个点WA,我只有最后一个点AC

P2357守墓人参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lp15gedr
此快照首次捕获于
2023/11/16 20:10
2 年前
此快照最后确认于
2023/11/16 21:19
2 年前
查看原帖
CPP
#include <stdio.h>
#include <math.h>
#define re register
#define N 200009 //
typedef long long ll;

int L[N],R[N],pos[N];
ll a[N],add[N],sum[N];
void change(int l,int r,ll v){//ll v
	int p=pos[l],q=pos[r];
	if(p==q){
		for(re int i=l;i<=r;i++)a[i]+=v;
		sum[p]+=v*(r-l+1);
	}
	else {
		for(re int i=p+1;i<=q-1;i++)add[i]+=v;
		for(re int i=l;i<=R[p];i++)a[i]+=v;
		sum[p]+=v*(R[p]-l+1);
		for(re int i=L[q];i<=r;i++)a[i]+=v;
		sum[q]+=v*(r-L[q]+1);
	}
}
ll ask(int l,int r){
	int p=pos[l],q=pos[r];
	ll ans=0;
	if(p==q){
		for(re int i=l;i<=r;i++)ans+=a[i];
		ans+=add[p]*(r-l+1);
	}
	else {
		for(re int i=p+1;i<=q-1;i++)
			ans+=sum[i]+add[i]*(R[i]-L[i]+1);
		for(re int i=l;i<=R[p];i++)ans+=a[i];
		ans+=add[p]*(R[p]-l+1);
		for(re int i=L[q];i<=r;i++)ans+=a[i];
		ans+=add[q]*(r-L[q]+1);
	}
	return ans;
}
int main(){
	int n,f;scanf("%d%d",&n,&f);
	for(re int i=1;i<=n;i++)scanf("%lld",&a[i]);
	int t=sqrt(n);//预处理
	for(re int i=1;i<=n;i++)
		L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)t++,L[t]=R[t-1]+1,R[t]=n;
	for(re int i=1;i<=t;i++)
		for(re int j=L[i];j<=R[i];j++)
			pos[j]=i,sum[i]+=a[i];
	for(re int i=1;i<=f;i++){
		int op;scanf("%d",&op);
		switch(op){
			ll l,r,k;
		case 1:
			scanf("%lld%lld%lld",&l,&r,&k);
			change(l,r,k);break;
		case 2:
			scanf("%lld",&k);change(1,1,k);break;
		case 3:
			scanf("%lld",&k);change(1,1,-k);break;
		case 4:
			scanf("%d%d",&l,&r);
			printf("%lld\n",ask(l,r));break;
		case 5:
			printf("%lld\n",a[1]);
		}
	}
	
	return 0;
}
pitY8fJ.png

回复

0 条回复,欢迎继续交流。

正在加载回复...