社区讨论
为啥别人都是最后一个点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;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...
