线段树板子求调
查看原帖
线段树板子求调
139509
liufukang楼主2021/8/22 15:02

WA了3个点,确实看不出来哪错了

#include<bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
#define mid (l+r>>1)//预定义左孩子、右孩子和中间位置
using namespace std;
typedef long long ll;
const int maxN=1e6+9;
ll n,m,tree[maxN<<2],lazy[maxN<<2];
ll read(){
	ll s=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (isdigit(ch)){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
void write(ll x){
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10^48);
}
void build(int k,int l,int r){
	if (l==r){
		tree[k]=read();
		return;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	tree[k]=tree[ls]+tree[rs];
}//建树
void pushdown(int k,int l,int r){
	if (!lazy[k]) return;//如果没有懒标记则跳过
	lazy[ls]+=lazy[k];lazy[rs]+=lazy[k];
	tree[ls]+=(mid-l+1)*lazy[k];
	tree[rs]+=(r-mid)*lazy[k];//将懒标记分给左右子树
	lazy[k]=0;//懒标记清零
}
void update(int k,int l,int r,int x,int y,ll v){
	if (x>r||y<l) return;//若当前范围与目标范围无关则跳过
	if (x<=l&&y>=r){
		tree[k]+=(r-l+1)*v;
		lazy[k]+=v;
		return;
	}//若当前范围覆盖目标范围则直接更新tree与懒标记
	pushdown(k,l,r);//下传懒标记
	update(ls,l,mid,x,y,v);
	update(rs,mid+1,r,x,y,v);//更新左右子树
	tree[k]=tree[ls]+tree[rs];//更新tree
}
int query(int k,int l,int r,int x,int y){
	if (x>r||y<l) return 0;//若当前范围与目标范围无关则跳过
	if (x<=l&&y>=r) return tree[k];//若当前范围覆盖目标范围则直接输出tree
	pushdown(k,l,r);//下传懒标记
	return query(ls,l,mid,x,y)+query(rs,mid+1,r,x,y);//查询左右子树
}
int main(){
	n=read(),m=read();
	build(1,1,n);
	while (m--){
		int op=read(),x=read(),y=read();
		if (op<2){
			ll v=read();
			update(1,1,n,x,y,v);
		}
		else{
			write(query(1,1,n,x,y));
			puts("");
		}
	}
	return 0;
}

感谢!

2021/8/22 15:02
加载中...