线段树爆零
  • 板块P2357 守墓人
  • 楼主hbhz_zcy
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/7/7 09:12
  • 上次更新2023/11/4 18:30:40
查看原帖
线段树爆零
142549
hbhz_zcy楼主2021/7/7 09:12

我线段树差不多快忘光了,脚造的代码,请耐心理解

能通过样例,但是提交全WA,找不到错误。

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
const int maxn=2e5+10;
LL m,a[maxn];
struct node{int l,r;LL v,lazy;}f[4*maxn];
void pushdown(int t){f[t].v=f[t<<1].v+f[t<<1|1].v;}
void pushup(int t){
	if(!f[t].lazy)  return;
	f[t<<1].v+=f[t].lazy*(f[t<<1].r-f[t<<1].l+1);
	f[t<<1|1].v+=f[t].lazy*(f[t<<1|1].r-f[t<<1|1].l+1);
	f[t<<1].lazy+=f[t].lazy,f[t<<1].lazy+=f[t].lazy;
	f[t].lazy=0;return;
}
void build(int t,int l,int r){
	f[t].l=l,f[t].r=r;
	if(l==r){f[t].v=a[l];return;}
	int m=(l+r)/2;
	build(t<<1,l,m),build(t<<1|1,m+1,r);
	pushdown(t);
	return;
}
void add(int t,int ul,int ur,LL x){
	int l=f[t].l,r=f[t].r;
	if(ur<l||ul>r)  return;
	if(l==r){f[t].v+=x;return;}
	if(ul<=l&&r<=ur){f[t].v+=x*(r-l+1),f[t].lazy+=x;return;}
	int m=(l+r)/2;pushup(t);
	if(ul<=m)  add(t<<1,ul,ur,x);
	if(ur>m)  add(t<<1|1,ul,ur,x);
	pushdown(t);
	return;
}
LL getsum(int t,int ul,int ur){
	int l=f[t].l,r=f[t].r;
	if(ul<=l&&r<=ur)  return f[t].v;
	if(r<ul||ur<l)  return 0;
	int m=(l+r)/2;LL rt=0;
	pushup(t);
	if(ul<=m)  rt+=getsum(t<<1,ul,ur);
	if(ur>m) rt+=getsum(t<<1|1,ul,ur);
	return rt;
}
int main(){
	int n,q;scanf("%d%d%lld",&n,&q,&m);
	for(int i=2;i<=n;i++)  scanf("%lld",&a[i]);
	build(1,1,n);
	while(q--){
		int q2;scanf("%d",&q2);
		if(q2==1){
			int l,r;LL k;scanf("%d%d%lld",&l,&r,&k);
			if(l==1){m+=k;add(1,2,r,k);}
			else  add(1,l,r,k);
		}
		if(q2==2){LL k;scanf("%lld",&k);m+=k;}
		if(q2==3){LL k;scanf("%lld",&k);m-=k;}
		if(q2==4){
			LL ans;int l,r;scanf("%d%d",&l,&r);
			if(l==1)  ans=m+getsum(1,2,r);
			else ans=getsum(1,l,r);
			printf("%lld\n",ans);
		}
		if(q2==5)  printf("%lld\n",m);
	}
	return 0;
}
2021/7/7 09:12
加载中...